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


Кафедра математической логики была основана в апреле 1959 г.

Первым заведующим кафедрой был А. А. Марков, затем кафедру возглавляли А. Н. Колмогоров и В. А. Мельников. В настоящее время кафедрой заведует В. А. Успенский.

В 1992 г. кафедра математической логики получает новое название — кафедра математической логики и теории алгоритмов.

В 1995 г. при кафедре организована Лаборатория логических проблем информатики.


НЕКОТОРЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ

В 1947 г. А. А. Марков доказал (независимо от Э. Поста, 1947 г.) алгоритмическую неразрешимость проблемы тождества слов в теории полугрупп. А. А. Марковым также установлена неразрешимость многих других известных алгоритмических проблем (в частности, неразрешимость проблемы гомеоморфии полиэдров, 1958 г.), ему принадлежит понятие нормального алгоритма.

А. Н. Колмогоров предложил интерпретацию интуиционистской логики как логики проблем (интерпретация Брауэра — Гейтинга — Колмогорова, 1925 г.). Он заложил основы теории нумераций и теории сложности конструктивных объектов (колмогоровская сложность, 1965 г.). А. Н. Колмогоров ввел очень широкое понятие алгоритма (машина Колмогорова — Успенского).

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

В 1955 г. С. И. Адян установил алгоритмическую неразрешимость проблем распознавания для почти всех инвариантных свойств групп и полугрупп. В 1968 г. С. И. Адян и П. С. Новиков доказали бесконечность нециклических свободных периодических групп нечетного периода n>664 (решение известной проблемы Бернсайда). В 1971 г. С. И. Адяном построен пример неабелевой группы без кручения, в которой пересечение любых двух подгрупп бесконечно.

Имеется также информация о научных результатах лаборатории логических проблем информатики.


Адрес: http://lpcs.math.msu.su/rus/history.htm
Изменения внесены 22.03.2013.
Мати Рейнович Пентус