Книга содержит изложение современного состояния теории рекурсивных функций и обзор основных приложений этой теории. В ней прослежено развитие теории рекурсивных функций, начиная с ее зарождения в тридцатых годах и кончая результатами исследований самых последних лет.
Не предполагающая в основной своей части никаких предварительных знаний, кроме знакомства с теоретико-множественной терминологией, книга Роджерса написана хорошим, ясным языком; при этом формальному изложению предпосылаются содержательные рассуждения, разъясняющие природу вводимых понятий или идей построений и доказательств; в ней содержится очень много упражнений.
Книга рассчитана на читателей, интересуйщихся современными проблемами математической логики и теории алгоритмов. Она доступна аспирантам и студентам старших курсов университетов и пединститутов.
Author(s): Роджерс Х. (авт.); Душский В.А., Канович М.И., Ногина Е.Ю. (перевод с англ.); Успенский В.А. (ред.)
Publisher: Мир
Year: 1972
Language: Russian
Commentary: обработана исходная книга (по 2 листа на разворот), но некоторые её недостатки остались, например, обрезан справа текст на стр. 48, 58, 60, 62, 64, 66, и далее на чётных.
Pages: 624
От редактора перевода 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-rc-теорема 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. Рекурсивные и рекурсивно перечислимые отношения; кодирование n-ок 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. Рекурсивные операторы 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. РЕШЕТКА РЕКУРСИВНО ПЕРЕЧИСЛИМЫХ МНОЖЕСТВ 286
§ 12.1. Решетки множеств 286
§ 12.2. Разложение 294
§ 12.3. Сжатые множества 296
§ 12.4. Максимальные множества 300
§ 12.5. Подмножества максимальных множеств 303
§ 12.6. Свойства почти-конечности 308
§ 12.7. Упражнения 316
Глава 13. СТЕПЕНИ НЕРАЗРЕШИМОСТИ 326
§ 13.1. Операция скачка 326
§ 13.2. Некоторые важные множества и степени 336
§ 13.3. Полные степени; категории и мера 341
§ 13.4. Упорядочение степеней 351
§ 13.5. Минимальные степени 355
§ 13.6. Частичные степени 359
§ 13.7. Решетка Медведева 363
§ 13.8. Дальнейшие результаты 372
§ 13.9. Упражнения 380
Глава 14. АРИФМЕТИЧЕСКАЯ ИЕРАРХИЯ (ЧАСТЬ 1) 387
§ 14.1. Иерархия множеств 387
§ 14.2. Нормальные формы 391
§ 14.3. Алгоритм Тарского — Куратовского 394
§ 14.4. Арифметическая представимость 400
§ 14.5. Сильная теорема об иерархии 403
§ 14.6. Степени 406
§ 14.7. Приложения в логике 408
§ 14.8. Вычислимые степени неразрешимости 415
§ 14.9. Упражнения 425
Глава 15. АРИФМЕТИЧЕСКАЯ ИЕРАРХИЯ (ЧАСТЬ 2) 429
§ 15.1. Иерархия классов множеств 429
§ 15.2. Иерархия классов функций 444
§ 15.3. Функционалы 459
§ 15.4. Упражнения 471
Глава 16. АНАЛИТИЧЕСКАЯ ИЕРАРХИЯ 478
§ 16.1. Аналитическая иерархия 478
§ 16.2. Аналитическое представление; приложения к логике 492
§ 16.3. Деревья с конечными путями 502
§ 16.4. Π11-множества и Δ11-множества 508
§ 16.5. Обобщенная вычислимость 515
§ 16.6. Гиперстепени и гиперскачок; Σ12 множества и Δ12 множества 523
§ 16.7. Результаты о базисе и неявная определимость 535
§ 16.8. Гиперарифметическая иерархия 556
§ 16.9. Упражнения 570
Литература 587
Указатель обозначений 600
Указатель теорем 602
Алфавитный указатель 606
ОГЛАВЛЕНИЕ 622
