22 апреля 1957 г. Комитет по Ленинским премиям в области науки и техники при Совете Министров СССР опубликовал первое послевоенное постановление о присуждении Ленинских премий за выдающиеся работы в области науки и техники.
Из математиков Ленинской премии удостоен замечательный ученый нашего времени, действительный член Академии наук СССР Новиков Петр Сергеевич за свой научный труд «Об алгоритмической неразрешимости проблемы тождества слов в теории групп».
Алгоритмом называют единое правило (предписание), позволяющее указать путь решения для любой задачи из серии однотипных задач. Примером алгоритма может служить правило перемножения натуральных чисел. Если человек владеет общим правилом перемножения двух натуральных чисел и может перемножать и складывать однозначные натуральные числа, то он сможет перемножить два любых натуральных числа. Широко известен алгоритм нахождения общего наибольшего делителя двух натуральных чисел путем последовательного деления (алгоритм Евклида).
Наличие алгоритма позволяет автоматизировать — нередко говорят — механически проводить — различные вычислительные процессы, связанные с решением серии однотипных задач. Если найден алгоритм решения серии однотипных задач, то можно построить машину, способную решить любую из этих задач (алгоритм позволяет составить программу, согласно которой машина будет решать каждую такую задачу). Если алгоритм разработать невозможно, иначе говоря, если он не существует, то построить такого рода машину нельзя. Конечно, это не означает, что для каждой из таких задач не существует свой способ решения, нет только единого метода их решения.
Вопросы, связанные с нахождением (разработкой) или с доказательством несуществования алгоритмов для решения задач тех или иных серий однотипных задач, называются алгоритмическими проблемами. Алгоритмические проблемы исследуются в одной из отраслей математической логики — в теории алгоритмов, имеющей теперь большое теоретическое и практическое значение (в первую очередь для машинной математики).
Приведенное выше определение алгоритма не является точным; оно чисто описательное. Благодаря этому разработка алгоритмических проблем продолжительное время не могла быть развернута во всей полноте. Если для какого-либо круга задач алгоритм не существовал, отсутствие точного определения алгоритма не позволяло дать этому факту научное доказательство. В 30-е годы точное определение алгоритма было, наконец, разработано. Благодаря этому удалось установить наличие алгоритмически неразрешимых задач как в математической логике, так и в математике (Марков, Пост). Однако относительно некоторых математических алгоритмических проблем долгое время не удавалось выяснить, разрешимы они или нет. К их числу относилась и проблема тождества слов в теории групп играющей фундаментальную роль в различных разделах математики. В самой теории групп эта алгоритмическая проблема была узловой: от ее решения зависело решение других важных вопросов теории групп.
Группой называют каждое множество элементов любой природы (чисел, движений и т. п.), для которых установлено одно прямое действие, называемое обычно перемножением и подчиняющееся закону ассоциативности, и обратное действие — деление. Каждый элемент группы является произведением элементов некоторого их исходного запаса. Последние называются образующими группы и обозначаются различными символами, например буквами алфавита. Результат перемножения образующих а и b записывают с помощью этих же букв, поставленных рядом: ab. Требование ассоциативности означает, что для любых элементов группы a,b,c: (ab)c = a(bc).
Образующие группы называются алфавитом, а каждое их произведение - словом. В группах можно разными способами определить равенство слов. Это определение может состоять из одной или конечной системы равенств между словами.
Проблема тождества слов была поставлена в 1912 году. Теперь ее формулировали так: пусть дана группа с конечным числом образующих и с конечным числом определяющих соотношений. Требуется построить алгоритм, позволяющий для любых двух слов установить, равны они между собой или нет.
В некоторых частных случаях, например, когда задается только одно определяющее соотношение. Эту проблему удалось решить.
Однако в общем случае вопрос о существовании алгоритма для решения проблемы тождества слов оставался открытым. В 1955 году П. С. Новиков опубликовал названную выше работу, в которой доказал, что существуют группы, для которых нет алгоритма, решающего проблемы тождества слов. Этот результат позволил П. С. Новикову установить неразрешимость других алгоритмических проблем теории групп: проблемы сопряженности и проблемы изоморфизма. Следуя идеям П. С. Новикова, некоторые математики (в том числе его ученики) решили ряд других алгоритмических проблем и получили значительные результаты.
Важнейшие результаты П. С. Новикова относятся к области математической логики, к которой его привел детальный анализ трудностей, встретившихся в теории множеств. Занимаясь математической логикой, П. С. Новиков старается выяснить роль и значение логических принципов в современной математике. В этом направлении им получен ряд интересных результатов, в том числе и результаты в вопросах приложения математической логики непосредственно к задачам теории множеств. Помимо замечательных работ в области математической логики и теории функций, П. С. Новикову принадлежит также работа в области теории Ньютоновского потенциала, имеющая принципиальное значение в современной геофизике.
