|
ОГЛАВЛЕНИЕ
От редактора перевода...................... 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. Упражнения..................
Литература..........................
Указатель обозначений...............
Указатель теорем....................
Алфавитный указатель................
|
2024. 288 с. Мягкая обложка. 15.9 EUR Новинка недели!
Особенности 20-го выпуска: - исправили предыдущие ошибки - Добавлены разновидности в раздел разновидностей юбилейных монет СССР - В раздел 50 копеек 2006-2015 добавлены немагнитные 50 копеек 10 копеек 2005 М (ввел доп. разворот) - Добавлена информация о 1 рубле 2010 СПМД немагнитный... (Подробнее) 
2024. 720 с. Твердый переплет. 19.9 EUR
Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее) 
2022. 1656 с. Твердый переплет. 169.9 EUR
Впервые в свет выходит весь комплекс черновиков романа М. А. Булгакова «Мастер и Маргарита», хранящихся в научно-исследовательском отделе рукописей Российской государственной библиотеки. Текст черновиков передаётся методом динамической транскрипции и сопровождается подробным текстологическим... (Подробнее) 
2023. 274 с. Мягкая обложка. 14.9 EUR
Арабо-израильский конфликт, в частности палестино-израильский, на протяжении многих десятилетий определял политическую ситуацию на Ближнем Востоке. На современном этапе наблюдается падение значимости палестинской проблемы в системе международных приоритетов основных акторов. В монографии... (Подробнее) 
URSS. 2024. 136 с. Мягкая обложка. В печати
В настоящей книге, написанной выдающимся тренером А.Н.Мишиным, описывается техника фигурного катания, даются практические советы по овладению этим видом спорта. В книге рассматриваются основы техники элементов фигурного катания и то, как эти элементы соединяются в спортивные программы, излагаются... (Подробнее) 
2024. 400 с. Твердый переплет. 16.9 EUR
Как реализовать проект в срок, уложиться в бюджет и не наступить на все грабли? Книга Павла Алферова — подробное практическое руководство для всех, кто занимается разработкой и реализацией проектов. Его цель — «переупаковать» проектное управление, сделать метод более применимым к российским... (Подробнее) 
URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) 
URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) 
URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) 
URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) |
Есть также в другом состоянии:
