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