markov_teorija_algorifmov (522344), страница 3
Текст из файла (страница 3)
Эрбрана и К. Геделя. ° ") Фииитиые хомбииаториые процессы Поста имеют большое сходство с машинами Тьюринга, хотя и были определеиы независимо от иих. чччч) Интересное изложение истории этого вопроса можно найти у С. К. Клиии в [б). шимости для классического исчисления предикатов, которую в то время Д. Гильберт считал главной проблемой математической логики. В 1947 г.
А. А. М а р к о в ы м [5), [6) и Э. Л. Постом [2) независимо друг от друга была установлена неразрешимость проблемы Туэ — проблемы тождества для полугрупп. Тем самым был указан первый пример неразрешимой алгорифмической проблемы собственно математического (не математико-логического) характера. В 1945 г. С. К. Кл и н и [31, используя уточненное понятие алгорифма, дал интерпретацию интуиционистской арифмети.
ки, чем радикально продвинул разработку основ конструктивной семантики. Эта работа Клини внесла существенныи вклад в развитие конструктивной логики. А. А.Марков от. мечал, что она оказала сильное влияние на эволюцию его взгля. дов на проблемы обоснования математики *). С первых же шагов теории алгорифмов (Т ь ю р и н г П1, [21) начались исследования, направленные на выяснение степе. ни эффективности ряда фундаментальных понятий и конструк ций математического анализа, С течением времени эти иссле. дования привели с созданию так называемого «конструктив.
ного математического анализа», который в своем построени» основывается не на отягощенных известными трудностями тра диционных концепциях теории множеств, а на значительно бо лее отчетливой (по крайней мере в принципиальном отношении основе — на уточненном понятии алгорифма и на конструктив ном понимании математических суждений «е). С тех пор с понятием алгорифма в математике оказалис1 связанными многие замечательные достижения.
Наряду с полу ченными конкретными результатами были выработаны так)ю некоторые важные общие представления. В частности, подтвер жденная Ю. В. М а т и я с е в и ч е м [2) гипотеза М. Девис, о совпадении рекурснвно перечислимых множеств с диофанто выми вскрыла Особое положение, которое В математике пани мают полиномы, то есть, по существу говоря, первоначальны~ арифметические действия — сложение и умножение.
Особен но возросла роль понятия алгорифма в связи с появление» электронных вычислительных машин и развитием вычисли тельной математики. Сознавая, однако, невозможность сколь е) Подробиый анализ этих взглядов читатель найдет в юбилейио статье Н. М. Н а г о р и о г о и Н. А. Ш а и и я а 11). *') Ряд результатов и характерных для иоиструитивиого анализа пс стаиовои задач излагается в специальной — девятой — главе пашей Киигв 12 ПРЕДИСЛОВИЕ ПРЕДИСЛОВИЕ ко-нибудь полного охвата*) относящейся к этому понятию проблематики, мы решили ограничиться в нашей книге изложением лишь некоторых, наиболее важных фактов общей теории алгорифмов, сопроводив его рядом приложений этой теории к конкретным математическим ситуациям.
Значительное внимание при этом мы уделяем логическому анализу применяемых средств. В качестве основы изложения в данной книге приняты нормальные алгорнфмы Маркова**). Они представляют собой уточнение общего понятия алгорифма, найденное А. А. Марковым в ходе поисков возможно более простого изложения егоуже упоминавшегося решения проблемы Туэ. Математик, знакомящийся с опубликованным А. А. Марковым решением и не вполне осведомленный относительно того, каким образом оио было получено, часто бывает удивлен сравнительной просто»ой, с которой этот результат достигается. Однако ощущение это обманчиво.
Не следует забывать, что прозрачность и изящество чрезвычайно глубокого по замыслу доказательства теоремы о представлении нормальных алгорифмов ассоциативными исчислениями ***), играющей в рассматриваемом круге вопросов центральную роль, явились следствием блестяще выбранного определения нормального алгорифма и что доказательство ее первоначального варианта, основанное на исчислении Х-конверсий, было куда более громоздким и сложным. Как это и естественно было предполагать, нормальные алгорифмы оказались эквивалентными рекусивным функциям (см. В.
К. Д е т л о в с П ]), а потому и другим ранее произведенным уточнениям. В развернутом виде теория нормальных алгорифмов впервые была изложена А. А. Марковым в его теперь уже ставшей классической монографии [2] е е е «). Понятие нормального алгорифма, обладающее многими достоинствами как принципиаль° 1 и ) Читатс.чю можно рекомеидовать обзор В.
А. У с п е яих же обзора [Ц. с к о г о и А. Л. С е и е я о а а [2], явля|ошийся переработанной версией ) Другие уточнения понятия алгорифма нами ие рассматриваются. Читатель может яозиакоииться с иими по книгам Д. Г и л ь б е р т а и П. Бернайса [1~, [2], С. К. К л и я и [5], А. И. Мальцева [Ц, Ю. И. М Ю, анина [1,Э.Меидельсоиа Ц,Р.Петер[В, Х.Родж е Р с а [ц, В. А.уУ,с п е и с к о г о [2], [3]. еь') В пашей кииге ато — теорема й 58.1 1.
'«") Определение нормального алгорифма, примеры и краткий очерк обшей теории были опубликоваиы ранее в его статье [Ц. ного, так н методического характера, оказалось плодотворным и удобным. Выдержав испьггание временем и доказав свою жизнеспособность, оно — наряду с понятиями рекурсивной функции и машины Тьюринга — прочно вошло в научный обиход современной теории алгорифмов. В частности, оно стало основным рабочим инструментом большой научйой школы, созданной и возглавлявшейся А.
А. Марковым. Вскоре после опубликования монография [2] была переведена на английский (дважды) и китайский языки. Однако русское ее издание, вышедшее небольшим тиражом, давно стало библиографической редкостью, и в практически доступной читателю научной и учебной литературе на русском языке теория нормальных алгорифмов в настоящее время имеется лишь в конспективном изложении, неизбежно не затрагивающем многих важных обстоятельств. Таким образом, потребность в новой книге по теории нормальных алгорифмов стала ощущаться уже давно. Она еще более возросла, когда возникла необходимость отразить некоторые новые появившиеся в этой теории подходы и результаты. Кроме того, со временем потребовалось перевести на язык нормальных алгорифмов ряд классических фактов общей теории, не нашедших в свое время отражения в монографии [2].
Проект написания книги, которая бы удовлетворяла эту потребность, обсуждался А. А. Марковым неоднократно, особенно в период его занятий ступенчатой семантической системой, которую теперь часто называют «башней Маркова». Критически анализируя общие проблемы возможного устройства конструктивной математики, А. А.
Марков настойчиво подчеркивал свою неудовлетворенность тем обстоятельством, что конструктивная логика, с одной стороны, и конкретные теории конструктивной математики — с другой, обычно излагаются раздельно, в известном отрыве друг от друга. Он указывал на необходимость поиска таких путей изложения, когда теория алгорифмов, конструктивная логика и продвинутые разделы конструктивной математики (на первых порах конкретно имелся в виду конструктивный математический анализ) излагались бы в рамках единой теории, основанной иа едином языке и на единой семантике этого языка. Собственно говоря, башня Маркова и была задумана как основа такой теории, объединяющая теорию алгорифмов с конструктивной логикой.
Изложению башни, естественно, должно было предшествовать изложение соответствукицим образом обработанной „общедоступной" теории нормальных алгорифмов. Будучи написано, оно затем могло бы быть использовано и для других ПРЕДИСЛОВИЕ целен (дальнейший Материал можно было бы выбирать В зави- симости от собственных склонностей, запланированного объе- ма книги и т д.). А.
А Марков трижды начинал работу над книгой, но тяже- лая болезнь не позволила ему в полной мере осуществить свой замысел. Один из вариантов рукописи был продвинут А. А. Марко- вым достаточно далеко. Своим глубоким замыслом и последо- вательностью, которой этот замысел реализуется, он произ- водит поразительное впечатление. Поражает сложная и вместе с тем прозрачная идея башни. Поражает неожиданное стремле- ние А.
А. Маркова сблизить — оставаясь в рамках конструк- Л, тивной концепции — свою точку зрения со взглядам — и , Э. Я. Брауэра. Поражает блистательно, с подлинным ху- дожественным мастерством выдержанный индуктивный стил и вложения (об этом впоследствии мы скажем более подробно). ь Этот вариант и положен мною в основу книги. Разумеется, . он допускал различные продолжения.
Конкретные очертания книга, к сожалению, приобрела уже тогда, когда А. А. Марко- : ва не было в живых. Окончательное решение относительно ее плана и и р шлось принять с учетом оставшихся рукописей Устных замечаний А. А. Маркова по поводу назначения и стиля '- планировавш " всвязиск с шейся книги и соображений, высказывавшихся и урсом теории алгорифмов, который я по его инициам тиве н польз 'ив ФТИ*. уясь его советами более двадцати раз читал в МГУ ). Я опирался также на ряд опубликованных работ аркови, и, разумеется, в первую очередь на его мононии.
азвание эт " грач' 121 которой у данной книги много общего в строе этой монографии я, чтобы подчеркнуть преемст- Ненность, рею~ ~ Р ~л сохранить и за вновь написанной книгой. строгаи продУманн аждому, кто изучал работы А. А. Маркова, известна их нх написанию и в т анность и тщательность, с которой он подходил , и в этом смысле книга, если бы она вышла при е1'О ЖИЗНИ, Во мно огом оказалась бы иной, чем оиа предстает перед читателем те теперь. Можно, однако, надеяться, что и в та- ком ее варианте он. на тоже не вызвала бы с его стороны слишком се ьезных нарекании Теперь следует с а а , я„дан„й сказать о некоторых существенных отлительно больш ™, что в ней уделяется значидно из ннх заключае ся в о, ~ас „~ „г ее че, ° ) Ма риал вгик лек лекций частично использован при Написании книгк.
ПРЕДИСЛОВИЕ ложення. В частности, в книгу введен ряд специальных параграфов (Я 1 — 16 *), 50, 67), посвященных чисто семантической стороне вопроса. Особенное внимание уделяется семантике импликации и отрицания — связок, понимание которых, как читатель будет иметь возможность убедиться, вызывает действительные трудности. Поскольку, однако, семантика в данной книге играет подчиненную роль, число семантических разъяснений по мере удаления от начала книги (и, значит, по мере возрастания опытности читателя) мы постепенно сводим „на нет", оставляя рутинные детали читателю. Параграф 67 посвящен рассмотрению чрезвычайно важного логического принципа конструктивной математики — так называемого «принципа конструктивного подбора».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
