|
ОГЛАВЛЕНИЕ
От редактора перевода...................... 5 Из предисловия автора...................... 7 Введение............................ 11 Глава 1. РЕКУРСИВНЫЕ ФУНКЦИИ............. 17 § 1.1. Неформальное понятие алгоритма.......... 17 § 1.2. Пример: примитивнорекурсивные функции 22 §.1.3. Экстенсиональность................. 25 § 1.4. Диагонализация.................. 27 § 1.5. Формализация................... 28 § 1.6. Основной результат....... 36 § 1.7. Тезис Чёрча.................... 38 § 1.8. Гёделевы номера, универсальность, s-m-ra-теорема... 39 § 1.9. Проблема остановки................ 43 § 1.10. Рекурсивность................... 46 Глава 2. НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ............ 53 § 2.1. Новые примеры неразрешимых проблем....... 53 § 2.2. Неразрешимые проблемы в других областях математики 56 § 2.3. Существование некоторых частично рекурсивных функций........................ 58 § 2.4. Исторические замечания.............. 60 § 2.5. Обсуждение.................... 61 § 2.6. Упражнения.................... 62 Глава 3. ЦЕЛИ КНИГИ И ЕЕ СОДЕРЖАНИЕ.......... 68 § 3.1. Задачи теории................... 68 § 3.2.. Направленность этой книги............ 70 § 3.3. Обзор содержания................. 71 Глава 4. РЕКУРСИВНАЯ ИНВАРИАНТНОСТЬ......... 73 § 4.1. Инвариантность относительно группы........ 73 § 4.2. Рекурсивные перестановки............. 74 § 4.3. Рекурсивная инвариантность............ 75 § 4.4. Сходство...................... 77 § 4.5. Универсальные функции.............. 77 § 4.6. Упражнения.................... 79 Глава 5. РЕКУРСИВНЫЕ И РЕКУРСИВНО ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА..................... 81 § 5.1. Определения.................... 81 § 5.2. Основная теорема.................. 84 § 5.3. Рекурсивные и рекурсивно перечислимые отношения; кодирование ге-ок.......... 89 § 5.4. Теоремы о проекции................ 92 § 5.5. Равномерность................... 95 § 5.6. Конечные множества................ 96 § 5.7. Теорема об однозначности.............. 99 § 5.8. Упражнения................. 101 Глава 6. СВОДИМОСТИ..................... 106 § 6.1. Общее введение.................... 106 § 6.2. Упражнения.................... 109 Глава 7. ОДНО-ОДНОСВОДИМОСТЬ; МНОГО-ОДНОСВОДИ-
МОСТЬ; ТВОРЧЕСКИЕ МНОЖЕСТВА........ 110
§ 7.1. Одно-односводимость и много-односводнмость.... 110
§ 7.2. Полные множества................. 113
§ 7.3. Творческие (креативные) множества......... 114
§ 7.4. Одно-одноэквивалентность и рекурсивный изоморфизм 116
§ 7.5. Одно-однополнота и много-однополнота........ 118
§ 7.6. Цилиндры..................... 121
§ 7.7. Продуктивность.................. 122
§ 7.8. Логика...................... 127
§ 7.9. Упражнения.................... 133
Глава 8. ТАБЛИЧНЫЕ СВОДИМОСТИ; ПРОСТЫЕ МНОЖЕСТВА 140
§ 8.1. Простые множества.................. 140
§ 8.2. Иммунные множества................ 142
§ 8.3. Табличная сводимость................ 145
§ 8.4. Табличная сводимость и много-односводимость.... 148
§ 8.5. Ограниченнотабличная сводимость.......... 150
§ 8.6. Структура степеней................ 155
§ 8.7. Другие рекурсивно перечислимые множества..... 158
§ 8.8. Упражнения.................... 160
Глава 9. СВОДИМОСТЬ ПО ТЬЮРИНГУ; ГИПЕРПРОСТЫЕ
МНОЖЕСТВА.................... 167
§ 9.1. Пример...................... 167
§ 9.2. Относительная рекурсивность............ 168
§ 9.3. Релятивизованная теория.............. 176
§ 9.4. Сводимость по Тьюрингу.............. 179
§ 9.5. Гиперпростые множества; теорема Деккера..... 181
§ 9.6. Сводимость по Тьюрингу и табличная сводимость;
проблема Поста......:............ 184
§ 9.7. Сводимость по перечислимости............ 189
§ 9.8. Рекурсивнв1е операторы............... 193
§ 9.9. Упражнения.................... 202
Глава 10. ПРОБЛЕМА ПОСТА; НЕПОЛНЫЕ МНОЖЕСТВА... 209
§ 10.1. Конструктивные подходы.............. 209
§ 10.2. Фридбергово решение................. 212
§ 10.3. Дальнейшие результаты и проблемы........ 217
§ 10.4. Неотделимые множества произвольной рекурсивно перечислимой степени.....220
§ 10.5. Теории произвольной рекурсивно перечислимой степени 222
§ 10.6. Упражнения.................... 226
Глава 11. ТЕОРЕМА О РЕКУРСИИ............... 232
§ 11.1 Введение...................... 232
§ 11.2. Теорема о рекурсии................ 233
§ 11.3. Полнота творческих множеств; вполне продуктивные
множества..................... 236
§ 11.4. Другие применения и конструкции......... 239
§ 11.5. Другие формы теоремы о рекурсии...... 249
§ 11.6. Обсуждение..................... 256
§ 11.7. Системы обозначений для ординалов......... 263
§ 11.8. Конструктивные ординалы............. 271
§ 11.9. Упражнения.................... 274
Глава 12. РЕШЕТКА РЕКУРСИВНО ПЕРЕЧИСЛИМЫХ МНОЖЕСТВ.
12.1. Решетки множеств.........
12.2. Разложение............
12.3. Сжатые множества.........
12.4. Максимальные множества......
12.5. Подмножества максимальных множеств
12.6. Свойства почти-конечности.....
12.7.. Упражнения.............
Глава 13. СТЕПЕНИ НЕРАЗРЕШИМОСТИ...........
§ 13.1. Операция скачка..................
§ 13.2. Некоторые важные множества и степени.......
§ 13.3. Полные степени; категории и мера.........
§ 13.4. Упорядочение степеней...............
§ 13.5. Минимальные степени...............
§ 13.6. Частичные степени.................
§ 13.7. Решетка Медведева.................
§ 13.8. Дальнейшие результаты...............
§ 13.9. Упражнения....................
Глава 14. АРИФМЕТИЧЕСКАЯ ИЕРАРХИЯ (ЧАСТЬ 1).....
§ 14.1. Иерархия множеств.................
§ 14.2. Нормальные формы...........•.....
§ 14.3. Алгоритм Тарского — Куратовского.........
§ 14.4. Арифметическая представимость...........
§ 14.5. Сильная теорема об иерархии............
§ 14.6. Степени.......................
§ 14.7. Приложения в логике...............
§ 14.8. Вычислимые степени неразрешимости........
§ 14.9. Упражнения....................
Глава 15. АРИФМЕТИЧЕСКАЯ ИЕРАРХИЯ (ЧАСТЬ 2).....
§ 15.1. Иерархия классов множеств.............
- § 15.2. Иерархия классов функций.............
§ 15.3. Функционалы...................
§ 15.4. Упражнения....................
Глава 16. АНАЛИТИЧЕСКАЯ ИЕРАРХИЯ...........
§ 16.1. Аналитическая иерархия..............
§ 16.2. Аналитическое представление; приложения, к логике
§ 16.3. Деревья с конечными путями............
§ 16.4. П^-множества и AJ-множества...........
§ 16.5. Обобщенная вычислимость..............
§ 16.6, Гиперстепени и гиперскачок; 2|-множества и Д|-мно-
жества.......................
§ 16.7. Результаты о базисе и неявная определимость....
§ 16.8. Гиперарифметическая иерархия...........
§ 16.9. Упражнения..................
Литература..........................
Указатель обозначений...............
Указатель теорем....................
Алфавитный указатель................
|