Рассказы о математиках

Приведенное выше определение алгоритма не является точным; оно чисто описательное. Благодаря этому разработка алгоритмических проблем продолжительное время не могла быть развернута во всей полноте. Если для какого-либо круга задач алгоритм не существовал, отсутствие точного определения алгоритма не позволяло дать этому факту научное доказательство. В 30-е годы точное определение алгоритма было, наконец, разработано. Благодаря этому удалось установить наличие алгоритмически неразрешимых задач как в математической логике, так и в математике (Марков, Пост). Однако относительно некоторых математических алгоритмических проблем долгое время не удавалось выяснить, разрешимы они или нет. К их числу относилась и проблема тождества слов в теории групп, играющей фундаментальную роль в различных разделах математики. В самой теории групп эта алгоритмическая проблема была узловой: от ее решения зависело решение других важных вопросов теории групп.

Группой называют каждое множество элементов любой природы (чисел, движений и т. п.), для которых установлено одно прямое действие, называемое обычно перемножением и подчиняющееся закону ассоциативности, и обратное действие — деление. Каждый элемент группы является произведением элементов некоторого их исходного запаса. Последние называются образующими группы и обозначаются различными символами, например буквами алфавита. Результат перемножения образующих а и Ь записывают с помощью этих же букв, поставленных рядом: ab. Требование ассоциативности означает, что для любых элементов группы α, β, γ

(α · β) γ = α (β · γ).

Образующие группы называются алфавитом, а каждое их произведение — словом. Например, если группа строится из трех образующих а, Ь, с, то такой алфавит позволяет составлять слова а, а^-1, а^-1Ь, ас, abbc и т. п. Перемножать можно не только отдельные буквы алфавита, но и слова. Так, из двух последних слов можно получить два новых слова; acabbc и abbcac (закона коммутативности ab = ba, вообще говоря, в группах нет).

В группах можно разными способами определить равенство слов. Это определение может состоять из одной или конечной системы равенств между словами. Так, если принять, что в группе (а, Ь, с) слова ab и bc равны: ab = bcb, то в каждом слове на место ab можно подставить bcb и наоборот. Благодаря этому можно утверждать, что слова abc и bcbc равны, или тождественны, между собой. Соотношение ab = bcb и ему подобные называют определяющими соотношениями группы.

Проблема тождества слов была поставлена в 1912 году. Теперь ее формулировали так: пусть дана группа с конечным числом образующих и с конечным числом определяющих соотношений. Требуется построить алгоритм, позволяющий для любых двух слов установить, равны они между собой или нет.

В некоторых частных случаях, например, когда задается только одно определяющее соотношение, эту проблему удалось решить. Однако в общем случае вопрос о существовании алгоритма для решения проблемы тождества слов оставался открытым. В 1955 году П. С. Новиков опубликовал названную выше работу, в которой доказал, что существуют группы, для которых нет алгоритма, решающего проблемы тождества слов. Этот результат позволил ученому установить неразрешимость других алгоритмических проблем теории групп: проблемы сопряженности и проблемы изоморфизма. Следуя идеям П. С. Новикова, некоторые математики (в том числе его ученики) решили ряд других алгоритмических проблем и получили значительные результаты.

Важнейшие результаты П. С. Новикова относятся к области математической логики, к которой его привел детальный анализ трудностей, встретившихся в теории множеств. Занимаясь математической логикой, П. С. Новиков старается выяснить роль и значение логических принципов в современной математике. В этом направлении им получен ряд интересных результатов, в том числе и результаты в вопросах приложения математической логики непосредственно к задачам теории множеств.

Помимо замечательных работ в области математической логики и теории функций, П. С. Новикову принадлежит также работа в области теории Ньютоновского потенциала, имеющая принципиальное значение в современной геофизике.

Иван Георгиевич Петровский (Род. в 1901 г.)