Василий Чистяков - Рассказы о математиках

Наличие алгоритма позволяет автоматизировать (нередко говорят — механически проводить) различные вычислительные процессы, связанные с решением серии однотипных задач. Если найден алгоритм решения серии однотипных задач, то можно построить машину, способную решить любую из этих задач (алгоритм позволяет составить программу, согласно которой машина будет решать каждую такую задачу). Если алгоритм разработать невозможно, иначе говоря, если он не существует, то построить такого рода машину нельзя. Конечно, это не означает, что для каждой из таких задач не существует свой способ решения, нет только единого метода их решения.

Вопросы, связанные с нахождением (разработкой) или с доказательством несуществования алгоритмов для решения задач, тех или иных серий однотипных задач, называются алгоритмическими проблемами. Алгоритмические проблемы исследуются в одной из отраслей математической логики — в теории алгоритмов, имеющей теперь большое теоретическое и практическое значение (в первую очередь для машинной математики).

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

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

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

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

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

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

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

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

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

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

Оторванный от учебы в университете, Петровский с жаром набросился на книги. Первой прочитанной научной книгой была теория чисел Дирихле. Эта книга, по выражению самого Ивана Георгиевича, «потрясла и навсегда повернула его интересы в сторону математики». Следующей научной книгой, за которую он взялся, была механика H. Е. Жуковского. Но осилить ее Петровский не мог — не хватало математических знаний. Из этого он делает вывод для себя: надо учиться и учиться прежде всего математике!

Вернувшись в Москву, молодой человек безо всяких колебаний переводится на математическое отделение Московского университета. Шел 1922 год. Учение приходилось сочетать с поисками средств для существования. Так, одно время будущий академик работал дворником в детском саду.