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

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

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

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

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

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

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

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

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

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

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

Тем не менее учение шло хорошо. Петровский по-настоящему увлекается математикой. После окончания университета он занимается в аспирантуре под руководством Д. Ф. Егорова, одного из прославленных деятелей отечественной науки.

Вся творческая жизнь И. Г. Петровского связана с Московским университетом — старейшим высшим учебным заведением нашей страны. В этом университете он был студентом и аспирантом, ассистентом и доцентом, профессором и заведующим кафедрой дифференциальных уравнений, деканом математико-механического факультета и, наконец, ректором университета. Этот пост ученый занимает в настоящее время. В 1943 году он избирается членом-корреспондентом Академии наук СССР, а через три года и ее действительным членом. С 1953 года академик Петровский — член президиума Академии наук СССР.

За выдающиеся научные заслуги в области создания общей теории дифференциальных уравнений И. Г. Петровскому в 1946 году присуждается Государственная премия СССР первой степени. Вторично лауреатом Государственной премии Иван Георгиевич стал за прекрасные учебные руководства по дифференциальным уравнениям, написанные им для высших учебных заведений. Эти учебники хорошо зарекомендовали себя, они несколько раз переиздавались у нас и переводились на многие иностранные языки.

Известно, что талантливым людям удается самые сложные теории облекать в доступную и увлекательную форму. Этим даром обладает и академик Петровский. Образцом такой доходчивости и являются его учебные книги: «Лекции по теории обыкновенных дифференциальных уравнений», «Лекции по теории интегральных уравнений» и «Лекции об уравнения с частными производными».

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