Научно-образовательный центр при МИАН

Алгоритмические проблемы в математике
академик Сергей Иванович Адян

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

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

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