|
F
(
n
)
,
проверяемого для всякого
п
конеч-
ным числом операций, из любого доказательства существования
числа
N
, для которого
F
(
N
)
истинно, можно извлечь эффективное
указание этого числа
N.
В 1947 г. Пётр Сергеевич исследовал вопрос о возможности
присоединения к исчислению предикатов без противоречия фор-
мул, постулирующих существование различных предикатов. Он на-
шел необходимые и достаточные условия для того, чтобы присо-
единение предиката
р
(
х
)
с одним переменным к исчислению пре-
дикатов не приводило к противоречию.
Пётр Сергеевич предпринял в теории алгоритмов исследова-
ния, навеянные проблематикой дескриптивной теории множеств.
Ещё в 1946 г. он обратил внимание своих учеников на «дескрип-
тивную» проблематику теории рекурсивных функций и высказал
основные предложения о классификации рекурсивно-проективных
множеств, об их отделимости, униформизации и т. п. Хотя эти ре-
зультаты не были опубликованы в то время и были независимо
получены и опубликованы другими авторами (Клини, Мостов-
ский), они оказали большое влияние на учеников Петра Сергееви-
ча и участников его семинаров, побудив их использовать эти «де-
скриптивные» явления в своих исследованиях, относящихся к
теории алгоритмов и её приложениям.
Как известно, после появления в математической логике точ-
ного определения понятия алгоритма выяснилось существование
неразрешимых алгоритмических проблем. Под алгоритмической
проблемой в математике понимается проблема отыскания алгорит-
ма для решения той или иной бесконечной серии однотипных за-
дач. Алгоритмическая проблема называется неразрешимой, если
искомый алгоритм не существует. Первые примеры неразрешимых
алгоритмических проблем были обнаружены в самой теории алго-
ритмов, а затем в математической логике. Естественно возникал
вопрос, не являются ли неразрешимые алгоритмические проблемы
специфическими для теории алгоритмов и математической логики.
Может быть, в традиционных разделах математики не бывает не-
разрешимых алгоритмических проблем? Нужно было исследовать
известные алгоритмические проблемы, которые не поддавались ре-
110
II. А.А. ЛЯПУНОВ О СВОИХ УЧИТЕЛЯХ, СОРАТНИКАХ, УЧЕНИКАХ
шению длительное время. После того как в 1947 г. А.А. Марков и
Э. Пост независимо установили неразрешимость проблемы тож-
дества для ассоциативных систем, особое внимание привлекала
проблема тождества слов теории групп, поставленная Дэном еще в
1912 г. В этой проблеме требовалось найти алгоритм, который поз-
волял бы проверить по любым двум словам группы, заданной с
помощью конечного числа образующих и определяющих соотно-
шений (такие группы называются конечно-определёнными), равны
они в этой группе или нет. Большие трудности, стоявшие на пути
решения этой проблемы, были связаны с тем, что группы с опре-
деляющими соотношениями почти не были исследованы. Более
того, была некоторая надежда, что алгоритм, решающий проблему
тождества, существенно облегчит исследование таких групп. И вот
в 1952 г. Пётр Сергеевич доказал неразрешимость этой проблемы,
построив пример конечно-определённой группы, для которой тре-
буемый алгоритм невозможен. Тот факт, что одну из центральных
теоретико-групповых проблем решил специалист по математичес-
кой логике, не является случайным. Дело в том, что группы с оп-
ределяющими соотношениями задаются посредством так назы-
ваемых групповых исчислений, которые родственны логическим
формальным системам. Успех был достигнут благодаря детальному
исследованию преобразований слов в групповых исчислениях.
Разработанный Петром Сергеевичем метод исследования пре-
образований слов в групповых исчислениях нашёл свое примене-
ние в дальнейших исследованиях алгоритмических проблем, пред-
принятых его учениками. Следствием неразрешимости проблемы
тождества является неразрешимость другой известной алгоритми-
ческой проблемы теории групп
–
проблемы сопряжённости. Пётр
Сергеевич доказал также неразрешимость очень важной для теории
групп проблемы изоморфизма. В этой проблеме требовалось найти
алгоритм, проверяющий для любой пары конечно-определённых
групп, изоморфны они или нет. Продолжая исследования Петра
Сергеевича, его ученик С.И. Адян доказал, что для каждой фикси-
рованной конечно-определённой группы Г невозможен алгоритм,
который проверял бы по произвольной группе, изоморфна она
группе Г или нет.
Результат Петра Сергеевича о неразрешимости проблемы тож-
дества теории групп и полученные затем следствия из него убеди-
тельно показали, что неразрешимые алгоритмические проблемы
широко распространены в математике и что они встречаются сре-
ди весьма актуальных алгоритмических проблем, касающихся фун-
даментальных понятий математики. В 1957 г. этот результат Петра
Сергеевича Новикова был удостоен Ленинской премии.
111
Пётр Сергеевич Новиков
Продолжая исследовать природу групповых исчислений, Пётр
Сергеевич заинтересовался одной из труднейших проблем теории
групп
–
проблемой Бернсайда о периодических группах. Эта про-
блема, сформулированная еще в 1902 г., заключалась в следующем:
будет ли конечной всякая группа с конечным числом образующих
и тождественным соотношением
Do'stlaringiz bilan baham: |
