100 лет со дня рождения

F 
(
n
)
, 
проверяемого для всякого 
п 
конеч-
ным числом операций, из любого доказательства существования 
числа 
N
, для которого 
F 
(
N
)
 
истинно, можно извлечь эффективное 
указание этого числа 
N.
В 1947 г. Пётр Сергеевич исследовал вопрос о возможности 
присоединения к исчислению предикатов без противоречия фор-
мул, постулирующих существование различных предикатов. Он на-
шел необходимые и достаточные условия для того, чтобы присо-
единение предиката 
р
(
х
)
 
с одним переменным к исчислению пре-
дикатов не приводило к противоречию.
Пётр Сергеевич предпринял в теории алгоритмов исследова-
ния, навеянные проблематикой дескриптивной теории множеств. 
Ещё в 1946 г. он обратил внимание своих учеников на «дескрип-
тивную» проблематику теории рекурсивных функций и высказал 
основные предложения о классификации рекурсивно-проективных 
множеств, об их отделимости, униформизации и т. п. Хотя эти ре-
зультаты не были опубликованы в то время и были независимо 
получены и опубликованы другими авторами (Клини, Мостов-
ский), они оказали большое влияние на учеников Петра Сергееви-
ча и участников его семинаров, побудив их использовать эти «де-
скриптивные» явления в своих исследованиях, относящихся к 
теории алгоритмов и её приложениям.
Как известно, после появления в математической логике точ-
ного определения понятия алгоритма выяснилось существование 
неразрешимых алгоритмических проблем. Под алгоритмической 
проблемой в математике понимается проблема отыскания алгорит-
ма для решения той или иной бесконечной серии однотипных за-
дач. Алгоритмическая проблема называется неразрешимой, если 
искомый алгоритм не существует. Первые примеры неразрешимых 
алгоритмических проблем были обнаружены в самой теории алго-
ритмов, а затем в математической логике. Естественно возникал 
вопрос, не являются ли неразрешимые алгоритмические проблемы 
специфическими для теории алгоритмов и математической логики. 
Может быть, в традиционных разделах математики не бывает не-
разрешимых алгоритмических проблем? Нужно было исследовать 
известные алгоритмические проблемы, которые не поддавались ре-

---

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

---

111
Пётр Сергеевич Новиков
Продолжая исследовать природу групповых исчислений, Пётр 
Сергеевич заинтересовался одной из труднейших проблем теории 
групп 
–
проблемой Бернсайда о периодических группах. Эта про-
блема, сформулированная еще в 1902 г., заключалась в следующем: 
будет ли конечной всякая группа с конечным числом образующих 
и тождественным соотношением