Аннотация

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

Программа курса

1. Введение. Понятие алгоритма и пример модели вычислимости: Машина Тьюринга. Тезис Чёрча-Тьюринга.
2. Вычислимые функции. Разрешимые и перечислимые множества. Теорема Поста.
3. Универсальная вычислимая функция. Универсальная Машина Тьюринга.
4. Проблема остановки и существование неразрешимых проблем.
5. m-сводимость.
6. Теорема Райса-Успенского.
7. Теорема Клини о неподвижной точке (теорема о рекурсии). И ее применения.
8. Напоминание логики предикатов. Формальная арифметика.
9. Представимость вычислимых функций в формальной арифметике. Гёделева нумерация.
10. Теорема Чёрча о неразрешимости формальной арифметики.
11. Теоремы Гёделя о неполноте.
12. Арифметическая иерархия.
13. Сводимость по Тьюрингу.
14. Примитивно-рекурсивные функции. Функция Аккермана.
15. Десятая проблема Гильберта и теорема Матиясевича. Примеры других неразрешимых задач в математике.

Пререквизиты

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

Литература

Верещагин Н.К., Шень А.  Вычислимые функции. (Серия «Лекции по математической логике и теории алгоритмов»)
Крупский В.Н. Теория алгоритмов. Введение в сложность вычислений.