ОГЛАВЛЕНИЕ

Предисловие .............. 3

Введение ............ 5

Глава I. Рекурсивные функции и алгоритмы...... 16

1. Интуитивная вычислимость............ 16

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

3. Образцы рекурсивности............. 25

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

5. Элементы рекурсивной геометрии .......... 39

6. Конструктивные объекты и алгоритмы......... 44

Глава II. Диофантовы множества и алгоритмическая неразрешимость 46

1. Основные результаты ...... 46

2. План доказательства............. 49

3. Перечислнмые множества являются D-множествами..... 51

4. Редукция.................. 53

5. Конструкция специального диофантова множества.....56

6. График экспоненты диофантов............ 61

7. Графики факториала и биномиальных коэффициентов диофантовы . 62

8. Дополнения................. 64

Глава III. Сложность и случайность.......... 65

1. Версальные семейства .............. 65

2. Сложность по Колмогорову............ 68

3. Сложность и случайность............. 73

Глава IV. Формальные языки и вычислимость....... 74

1. Арифметика синтаксиса............. 74

2. Синтаксический анализ............. 80

3. Перечислимость выводимых формул............ 85

Глава V. Теорема Геделя............. 87

1. Принцип неполноты.............. 87

2. Неперечислимость истинных формул.......... 88

3. О длине доказательств ............. 91

4. Арифметическая иерархия.............93

5. Продуктивность арифметической истины......... 96

6. Вычислимые функции с очень быстрым ростом.......99

Глава VI. Рекурсивные группы .........101

1. Основной результат и его следствия ........101

2. Свободные произведения и HNN-расширения.......104

.1 Вложения в группы с двумя образующими........107

4. Хорошие подгруппы.............. 108

5 Ограниченные системы образующих .......... 111

6. Окончание доказательства........ 116

Список литературы...............123

Именной указатель............. 125

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