На главную страницу НМУ

Л.Д.Беклемишев

Вычислимость, логика и теоремы Гёделя

1. Вычислимость: машины Тьюринга, вычислимые функции, перечислимые, разрешимые множества. Разрешимые и неразрешимые алгоритмические проблемы. Тезис Чёрча--Тьюринга.
2. Логика первого порядка, её язык, модели. Теоремы о полноте и компактности (без доказательства). Аксиоматические теории. Программа Гильберта.
3. Формальная арифметика, её язык и аксиомы. $\Sigma_1$-определимость как универсальная модель вычислимости.
4. Первая теорема Гёделя о неполноте. Её варианты и усиления. Неразрешимость исчисления предикатов.
5. Теорема о неподвижной точке в арифметике. Гёделевская формула доказуемости. Вторая теорема Гёделя о неполноте. Теорема Лёба.
6. Нестандартные модели арифметики. Теорема Тенненбаума.