Содержание

Предисловие 6

1. Вычислимость, разрешимость и перечислимость 8

1.1. Вычислимые функции ............ 8

1.2. Разрешимые множества ........... 9

1.3. Перечислимые множества.......... 10

1.4. Перечислимые и разрешимые множества   . 13

1.5. Перечислимость и вычислимость...... 14

2. Универсальные функции и неразрешимость 17

2.1. Универсальные функции........... 17

2.2. Диагональная конструкция ......... 18

2.3. Перечислимое неразрешимое множество . . 20

2.4. Перечислимые неотделимые множества  . . 21

2.5. Простые множества: конструкция Поста   . 22

3. Нумерации и операции 24

3.1. Главные универсальные функции...... 24

3.2. Вычислимые последовательности функций 28

3.3. Главные универсальные множества..... 29

4. Свойства главных нумераций 32

4.1. Множества номеров.............. 32

4.2. Новые номера старых функций....... 36

4.3. Изоморфизм главных нумераций...... 39

4.4. Перечислимые свойства функций...... 41

5. Теорема о неподвижной точке 45

5.1. Неподвижная точка и отношения эквивалентности................ 45

5.2. Программа, печатающая свой текст   .... 47

5.3. Системный трюк: ещё одно доказательство................. 50

5.4. Несколько замечаний............. 53

6. /«-сводимость и свойства перечислимых множеств 59

6.1. т-сводимость................. 59

6.2. т-полные множества............. 60

6.3. т-полнота и эффективная неперечислимость............... 62

6.4. Изоморфизм т-полных множеств...... 66

6.5. Продуктивные множества.......... 68

6.6. Пары неотделимых множеств........ 72

7. Вычисления с оракулом 76

7.1. Машины с оракулом.............. 76

7.2. Эквивалентное описание........... 79

7.3. Релятивизация................. 81

7.4. О'-вычисления................. 85

7.5. Несравнимые множества........... 88

7.6. Теорема Мучника-Фридберга: схема конструкции.................. 92

7.7. Теорема Мучника-Фридберга: выигрышные условия............. 94

7.8. Теорема Мучника-Фридберга: метод приоритета................... 96

8. Арифметическая иерархия 98

8.1. Классы £„ и П„................ 98

8.2. Универсальные множества в £„ и П„   ... 101

8.3. Операция скачка................ 102

8.4. Классификация множеств в иерархии   . . . 108

9. Машины Тьюринга 112

9.1. Зачем нужны простые вычислительные модели?..................... 112

9.2. Машины Тьюринга: определение...... 113

9.3. Машины Тьюринга: обсуждение ...... 115

9.4. Ассоциативные исчисления.......... 118

9.5. Моделирование машин Тьюринга...... 120

9.6. Двусторонние исчисления .......... 124

9.7. Полугруппы, образующие и соотношения  . 125

10. Лрифметичность вычислимых функций 129

10.1. Программы с конечным числом переменных................... 129

10.2. Машины Тьюринга и программы...... 132

10.3. Лрифметичность вычислимых функций . . 134

10.4. Теоремы Тарского и Гёделя......... 138

10.5. Прямое доказательство теорем Тарского

и Гёделя..................... 140

10.6. Арифметическая иерархия и перемены кванторов ................... 142

11. Рекурсивные функции 145

11.1. Примитивно рекурсивные функции..... 145

11.2. Примеры примитивно рекурсивных функций .................... 146

11.3. Примитивно рекурсивные множества   ... 147

11.4. Другие виды рекурсии............ 150

11.5. Машины Тьюринга и рекурсивные

функции .................... 153

11.6. Частично рекурсивные функции...... 155

11.7. Вычислимость с оракулом.......... 159

11.8. Оценки скорости роста.

Функция Аккермана ............. 162

Литература 166

Предметный указатель 168

Указатель имён 174