Станислав Олегович Сперанский

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

Предварительный план

1. Формализация понятия (частичной) вычислимой функции: машины Тьюринга, рекурсивные схемы и т.д. Тезис Чёрча—Тьюринга.
2. Разрешимые и полуразрешимые (вычислимо перечислимые) множества. Универсальные вычислимые функции. Проблемы самоприменимости и остановки.
3. Сводимость между алгоритмическими проблемами. Вычислимая неотделимость. Полнота проблемы самоприменимости в классе всех полуразрешимых множеств. О связи с 10-й проблемой Гильберта.
4. Полугруппы, заданные соотношениями. Проблема равенства в полугруппах. Теорема Маркова—Поста. Обзор результатов, связанных с проблемой равенства в группах.