Вычислимо перечислимые множества и степени

Соар Р.И. Вычислимо перечислимые множества и степени (2000) ......Page 1
Содержание ......Page 7
Предисловие редактора перевода ......Page 12
Предисловие автора к русскому изданию ......Page 14
Введение ......Page 17
Часть А. Фундаментальные понятия теории вычислимости ......Page 23
Глава I. Вычислимые функции ......Page 25
§ 1. Неформальное описание ......Page 26
2.1. Примитивно рекурсивные функции ......Page 27
2.2. Диагонализация и частично вычислимые функции ......Page 28
2.3. Вычислимые по Тьюрингу функции ......Page 30
§ 3. Основные результаты ......Page 34
§ 4. Вычислимо перечислимые множества и неразрешимые проблемы ......Page 39
§ 5. Вычислимые перестановки и теорема Майхилла об изоморфизме ......Page 46
§ 1. Эквивалентные определения вычислимо перечислимых множеств и их основные свойства ......Page 51
§ 2. Равномерность и индексы вычислимых и конечных множеств ......Page 58
§ 3. Теорема рекурсии ......Page 62
§ 4. Полные, продуктивные и креативные множества ......Page 68
§ 1. Определения относительной вычислимости ......Page 76
§ 2. Тьюринговы степени и оператор скачка ......Page 84
§ 3. Леммы о модуле и о пределе ......Page 89
§ 1. Уровни вычислимости в арифметической иерархии ......Page 94
§ 2. Теорема Поста и теорема об иерархии ......Page 98
§ 3. Σn-полные множества ......Page 101
§ 4. Релятивизованная арифметическая иерархия. Высокие и низкие степени ......Page 106
Часть В. Проблема Поста, оракульные конструкции и метод приоритета с конечными нарушениями ......Page 111
Глава V. Простые множества и проблема Поста ......Page 113
§ 1. Иммунные и простые множества. Конструкция Поста ......Page 114
§ 2. Гиперпростые множества и мажорирующие функции ......Page 117
§ 3. Метод разрешения ......Page 123
§ 4. Полнота эффективно простых множеств ......Page 126
§ 5. Критерий полноты для в. п. множеств ......Page 127
Глава VI. Оракульные конструкции не в. п. степеней ......Page 133
§ 1. Пара несравнимых степеней ниже О' ......Page 134
§ 2. Избегание конусов степеней ......Page 138
§ 3. Обращение скачка ......Page 139
§ 4. Верхние и нижние грани степеней ......Page 143
§ 5. * Минимальные степени ......Page 147
Глава VII. Метод приоритета с конечными нарушениями ......Page 156
§ 1. Низкие простые множества ......Page 157
§ 2. Исходная теорема Мучника-Фридберга ......Page 166
§ 3. Теоремы о разложении ......Page 170
Часть С. Бесконечные методы построения в. п. множеств и степеней ......Page 179
Глава VIII. Метод приоритета с бесконечными нарушениями ......Page 181
§ 1. Препятствия в методе приоритета с бесконечными нарушениями и лемма о густоте ......Page 182
§ 2. Леммы о нарушениях, об окнах и о сильной густоте ......Page 187
§ 3. Теорема о скачке ......Page 192
§ 4. Теорема плотности и стратегия кодирования Сакса ......Page 198
§ 5. * Модель пинбольной машины для метода бесконечных нарушений ......Page 204
Глава IX. Метод минимальных пар и вложение решеток в в. п. степени ......Page 208
§ 1. Минимальные пары и вложение ромба ......Page 209
§ 2. * Вложение дистрибутивных решеток ......Page 216
§ 3. Теорема о невложимости ромба ......Page 222
§ 4. * Неветвящиеся степени ......Page 231
§ 5. * Недополняемые вниз степени ......Page 238
§ 1. Идеалы, фильтры и факторрешетки ......Page 243
§ 2. Теоремы о разложении и булевы алгебры ......Page 247
§ 3. Максимальные множества ......Page 255
§ 4. Мажорные подмножества и r-максимальные множества ......Page 260
§ 5. Безатомные r-максимальные множества ......Page 266
§ 6. Безатомные гг-простые множества ......Page 271
§ 7. * Σ3-булевы алгебры, представимые в виде решеток надмножеств ......Page 275
Глава XI. Связи между структурой в. п. множества и его степенью ......Page 281
§ 1. Характеризация Мартина высоких степеней в терминах функций-доминант ......Page 282
§ 2. Максимальные множества и высокие в. п. степени ......Page 293
§ 3. Низкие в. п. множества похожи на вычислимые множества ......Page 304
§ 4. Не 2-низкие в. п. степени содержат безатомные в. п. множества ......Page 312
§ 5. * 2-Низкие в. п. степени не содержат безатомных в. п. множеств ......Page 317
Глава XII. Классификация индексных множеств в. п. множеств ......Page 326
§ 1. Классификация индексного множества G(A)={х: Wx ≡т А} ......Page 327
§ 2. Классификация индексных множеств G(≤А), G(≥А) и G(│А) ......Page 332
§ 3. Равномерное перечисление в. п. множеств и Σ3 индексные множества ......Page 341
§ 4. Классификация индексных множеств n-высоких, n-низких и промежуточных в. п. множеств ......Page 348
§ 5. Неподвижные точки по тьюринговой эквивалентности ......Page 361
§ 6. Обобщение теоремы рекурсии и критерия полноты на все уровни арифметической иерархии ......Page 364
Часть D. Дальнейшие разделы и современные области исследования в. п. степеней и решетки в. п. множеств ......Page 371
Глава XIII. Быстро простые множества. Совпадение классов в. п. степеней, и алгебраическое разложение в. п. степеней ......Page 373
§ 1. Быстро простые множества и степени ......Page 374
§ 2. Совпадение классов быстро простых степеней, недополняемых вниз степеней, и эффективно недополняемых вниз степеней ......Page 382
§ 3. Разложение в. п. степеней на непересекающееся объединение определимого идеала и определимого фильтра ......Page 391
§ 4. Дополняемые наверх степени и совпадение быстро простых и низко дополняемых наверх степеней ......Page 393
Глава XIV. Метод деревьев и 0'''-приоритетные рассуждения ......Page 398
§ 1. 0'-приоритетные рассуждения ......Page 399
§ 2. Метод деревьев в приоритетных рассуждениях и классификация 0', 0" и 0'''-приоритетных методов ......Page 403
3.1. Деревья в обычном 0" -приоритетном рассуждении ......Page 409
3.2. 0"-приоритетное рассуждение, требующее метод деревьев ......Page 410
4.1. Предварительные сведения ......Page 418
4.2. Основной модуль для удовлетворения подтребования (конструирование компьютерного чипа) ......Page 419
4.3. Приоритетное дерево (вычислительная архитектура машины) ......Page 424
4.4. Интуитивные описания приоритетного дерева и доказательство ......Page 430
4.5. Построение (операционная система машины) ......Page 431
4.6. Верификация ......Page 436
§ 1. Инвариантные свойства ......Page 446
§ 2. Некоторые основные свойства автоморфизмов решетки в. п. множеств ......Page 450
§ 3. Неинвариантные свойства ......Page 455
§ 4. Формулировка теоремы о расширении и его мотивация ......Page 458
§ 5. Удовлетворение условий теоремы о расширении для максимальных множеств ......Page 467
6.1. Машины ......Page 473
6.2. Построение ......Page 477
6.3. Требования и мотивация правил ......Page 478
6.4. Правила ......Page 481
6.5. Проверка ......Page 484
§ 1. Автоморфизмы и изоморфизмы решётки в. п. множеств ......Page 491
§ 2. Элементарная теория решётки в. п. множеств ......Page 498
§ 3. Элементарная теория в. п. степеней ......Page 503
§ 4. Алгебраическая структура R ......Page 506
Литература ......Page 510
Список обозначений ......Page 549
Предметный указатель ......Page 562