Вычислимое и невычислимое

Титульный лист ......Page 1
Выходные данные ......Page 2
Предисловие ......Page 3
Введение ......Page 5
1. Интуитивная вычислимость ......Page 16
2. Частично рекурсивные функции ......Page 20
3. Образцы рекурсивности ......Page 25
4. Перечислимые и разрешимые множества ......Page 29
5. Элементы рекурсивной геометрии ......Page 39
6. Конструктивные объекты и алгоритмы ......Page 44
1. Основные результаты ......Page 46
2. План доказательства ......Page 49
3. Перечислимые множества являются О-множествами ......Page 51
4. Редукция ......Page 53
5. Конструкция специального диофантова множества ......Page 56
6. График экспоненты днофантов ......Page 61
7. Графики факториала и биномиальных коэффициентов диофантовы ......Page 62
8. Дополнения ......Page 64
1. Версальные семейства ......Page 65
2. Сложность по Колмогорову ......Page 68
3. Сложность и случайность ......Page 73
1. Арифметика синтаксиса ......Page 74
2. Синтаксический анализ ......Page 80
3. Перечислимость выводимых формул ......Page 85
1. Принцип неполноты ......Page 87
2. Неперечислимость истинных формул ......Page 88
3. О длине доказательств ......Page 91
4. Арифметическая иерархия ......Page 93
5. Продуктивность арифметической истины ......Page 96
6. Вычислимые функции с очень быстрым ростом ......Page 99
1. Основной результат и его следствия ......Page 101
2. Свободные произведения и HNN-расширения ......Page 104
3. Вложения в группы с двумя образующими ......Page 107
4. Хорошие подгруппы ......Page 108
5 Ограниченные системы образующих ......Page 111
6. Окончание доказательства ......Page 116
Список литературы ......Page 123
Предметный указатель ......Page 125
Оглавление ......Page 127