В курсе будут рассказаны классические результаты теории вычислимости, связанные с именами Чёрча, Тьюринга, Гёделя, Клини, Поста и других великих логиков XX века. Курс будет состоять из восьми лекций, разбитых на пары.

Первый день: диагональный метод. Сначала мы познакомимся с понятиями разрешимого и перечислимого множества, изучим их основные свойства. Затем при помощи диагонального метода мы докажем существование перечислимых, но неразрешимых задач. Наиболее известной такой задачей является проблема остановки: остановится ли программа на данном входе? Наконец, при помощи техники m-сводимости мы докажем, что ни множество программ, которые останавливаются всюду, ни дополнение этого множества, не являются перечислимыми.

Второй день: теоремы о неподвижных точках. Оказывается, неразрешимы не только какие-то выделенные свойства программ. Неразрешимы вообще любые свойства, которые не зависят от текста программы, а зависят лишь от результата её работы. В этом заключается теорема Успенского-Райса. Она тесно связана с теоремой Клини: каким бы ни было преобразование программ, найдётся программа, которая до преобразования делает то же, что и после. Как следствие, в любом языке программирования можно написать программу, печатающую собственный текст.

Третий день: неразрешимые проблемы алгебры и логики. Неразрешимые проблемы, связанные с работой программ, весьма умозрительны. Может быть, эта теория не имеет отношения к остальной математике? Нет, имеет! Эти проблемы можно переформулировать в терминах других областей. Так, неразрешима проблема равенства в полугруппах (в этом заключается теорема Маркова-Поста), нельзя проверить формулу первого порядка на общезначимость (это теорема Чёрча), а колмогоровская сложность слова из нулей и единиц невычислима.