ВУЗ:
Составители:
Оглавление
Предисловие _________________________________________________________________5
1 Алгоритмы и вычислимые функции ________________________________________7
1.1 Понятие алгоритма и неформальная вычислимость ___________________________7
1.2 Частично-рекурсивные функции ____________________________________________8
Определения___________________________________________________________________________ 8
Примеры рекурсивности _________________________________________________________________ 9
1.3 Машины Тьюринга _______________________________________________________11
2 Вычислимое и невычислимое _____________________________________________15
2.1 Тезис Чёрча ______________________________________________________________15
2.2 Теорема о рекурсии _______________________________________________________16
2.3 Куины ___________________________________________________________________18
2.4 Некоторые алгоритмически неразрешимые проблемы ________________________20
3 Формальные аксиоматические теории ____________________________________24
3.1 Основные определения ____________________________________________________24
Что такое формальная теория? ___________________________________________________________ 24
Выводимость _________________________________________________________________________ 25
Интерпретация ________________________________________________________________________ 27
Общезначимость и непротиворечивость ___________________________________________________ 28
Полнота, независимость и разрешимость __________________________________________________ 29
3.2 Примеры формальных теорий ______________________________________________29
Формальная система MIU _______________________________________________________________ 29
Формальная система PR ________________________________________________________________ 30
Формальная система UR ________________________________________________________________ 31
Формальная система PR1 _______________________________________________________________ 31
3.3 Исчисление высказываний_________________________________________________32
Классическое определение исчисления высказываний _______________________________________ 32
Полнота, разрешимость и непротиворечивость исчисления ___________________________________ 32
высказываний_________________________________________________________________________ 32
3.4 Теории первого порядка ___________________________________________________33
Языки первого порядка _________________________________________________________________ 33
Синтаксические свойства истинности теорий с языком первого _______________________________ 34
порядка ______________________________________________________________________________ 34
Определение теории первого порядка _____________________________________________________ 34
Некоторые свойства теорий первого порядка _______________________________________________ 36
Непротиворечивость, полнота и неразрешимость исчисления _________________________________ 37
предикатов ___________________________________________________________________________ 37
4 Элементарная арифметика и неполнота __________________________________38
4.1 Элементарная арифметика _________________________________________________38
Теория элементарной арифметики ________________________________________________________ 38
Арифметические функции и отношения ___________________________________________________ 40
4.2 Неполнота элементарной арифметики_______________________________________41
Геделева нумерация____________________________________________________________________ 41
Лемма о рефлексии ____________________________________________________________________ 43
Теорема Гёделя о неполноте_____________________________________________________________ 44
Нестандартное расширение EA___________________________________________________________ 47
Об аксиоматизации ____________________________________________________________________ 48
4.3 Теорема Гудстейна ________________________________________________________50
