Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Традиции и наследие кафедры

Первый действующий семинар по математической логике существовал на мехмате МГУ с тридцатых годов XX века. Руководителями этого семинара были академик Петр Сергеевич Новиков, работавший в Математическом институте им. В. А. Стеклова (МИАН) и Московском государственном педагогическом институте им. В. И. Ленина (сейчас МПГУ), и профессора мехмата МГУ Софья Александровна Яновская и Иван Иванович Жегалкин. В наше время этот семинар функционирует как кафедральный семинар по математической логике и теории алгоритмов.

Решение о создании кафедры математической логики МГУ, а также одновременно с ней и отдела математической логики в МИАН, было принято на Третьем Всесоюзном математическом съезде. Кафедра была открыта в 1959 году, и первым её заведующим стал чл.-корр. АН СССР Андрей Андреевич Марков (мл.).

Отметим, что Математический институт РАН им. В. А. Стеклова (МИАН) является центром научных исследований в области математики в России, бесспорна и его роль во всей мировой математике. Профессор нашей кафедры, академик С.И. Адян руководит отделом математической логики МИАН, в котором работают и сотрудники нашей кафедры проф. Л. Д. Беклемишев, асс. С. Л. Кузнецов, В. В. Подольский. Плодотворное взаимодействие между кафедрой и отделом математической логики МИАН возникло со времени их основания и продолжает быть важным фактором для поддержания высокого уровня научных исследований в нашей области, для перспектив аспирантуры и для дальнейшей работы способных выпускников нашей кафедры, заинтересованных в продолжении научной деятельности и сильном научном руководстве. (Можно отметить, что в настоящее время из восьми сотрудников отдела семеро являются выпускниками нашей кафедры.)

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

А. Н. Колмогоров был автором первых результатов по математической логике в нашей стране, которые касались формализации интуиционистской логики и её интерпретации как «логики задач». В дальнейшем он (вместе со своим учеником В.А. Успенским) внес важный вклад в исследование понятия алгоритма и стал основоположником алгоритмической теории информации (колмогоровской сложности).

П. С. Новиков внес выдающийся вклад в теорию множеств, в теорию доказательств, исследование алгоритмических проблем в алгебре и комбинаторную теорию групп. Им была построена конечно определенная группа с неразрешимой проблемой равенства слов (решение так называемой проблемы слов в группах). Он был автором одного из первых учебников по математической логике в нашей стране «Элементы математической логики». Наконец, совместно со своим учеником С.И. Адяном, им была решена одна из труднейших математических проблем, имеющих многолетнюю историю — проблема Бернсайда о периодических группах.

Ан. А. Марков был основоположником традиции в основаниях математики, известной в мире как «русский конструктивизм». Ему принадлежит понятие алгорифма Маркова, одной из стандартных в настоящее время универсальных вычислительных моделей. Он также получил фундаментальные результаты, касающиеся неразрешимых алгоритмических проблем в математике: теорему о нераспознаваемости свойств конечно определенных полугрупп, а также теорему о нераспознаваемости гомеоморфизма топологических многообразий в размерностях больше четырех.

Ниже мы подробнее расскажем об основных направлениях работы кафедры.