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

История кафедры

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

  • Андрей Андреевич Марков (22.09.1903 — 11.10.1979).
    Первый заведующий кафедрой с 1959 г. по октябрь 1979 г. (одновременно заведующий лабораторией математической логики и структуры машин Вычислительного центра АН СССР). А. А. Марков — выдающийся российский математик, член-корреспондент АН СССР, плодотворно работавший в области алгебры, топологии, механики, математической логики и теории вычислимости, основоположник российской научной школы конструктивной математики.
  •  
  • Андрей Николаевич Колмогоров (25.04.1903 — 20.10.1987).
    Заведующий кафедрой с января 1980 г. по октябрь 1987 г. (одновременно заведующий отделением математики Механико-математического факультета МГУ). Великий математик, академик А. Н. Колмогоров является автором первой статьи на русском языке, содержащей результаты по математической логике (опубликована в 1925 г.). А. Н. Колмогоровым был получен ряд фундаментальных результатов в математической логике и ее приложениях.
  •  
  • Владимир Андреевич Мельников (18.08.1928 — 07.05.1993).
    Заведующий кафедрой с 1988 г. по май 1993 г. (одновременно директор Института проблем кибернетики АН СССР). Научная деятельность академика В. А. Мельникова охватывала целый спектр научных и технических проблем создания новых образцов вычислительной техники.
  •  
  • Владимир Андреевич Успенский (27.11.1930 — 27.06.2018).
    Заведующий кафедрой с января 1995 г. по июнь 2018 г. (и.о. заведующего кафедрой с октября 1993 г. по январь 1995 г.) В. А. Успенский начал свою научную деятельность, будучи студентом А. Н. Колмогорова, и все последующие годы продолжал работу по изучению и развитию колмогоровского наследия.

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

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

Некоторые научные результаты сотрудников кафедры

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

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

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

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