СИНТЕТИЧЕСКАЯ Омск: Изд-во ОмГУ, 2016. 152 стр. |
Излагаются элементы современной теории синтетической вычислимости. Дается представление об алгоритмах, рекурсивных функциях, интуиционизме, интуиционистской логике, конструктивной математике, реализуемости Клини, теории категорий, теории топосов, топосе реализуемости и др. Описываются эффективный топос Хайлэнда и рекурсивный топос Малри, в которых все функции f: N -> N и f: N^N -> N соответственно вычислимы.
Для студентов и аспирантов факультетов компьютерных наук, информационных технологий и математических факультетов.
Оглавление
Введение {9}
1. Вычислимость и алгоритмы {16}
1.1. Интуитивное определение алгоритма и вычислимой функции {16}
1.1.1. Определение алгоритма {16}
1.1.2. Определение вычислимой функции {18}
1.2. Рекурсивные функции Эрбрана-Геделя-Клини {18}
1.2.1. Примитивно рекурсивные функции {18}
1.2.2. Рекурсия и противоречивость теории {19}
1.2.3. Частично рекурсивные функции {20}
1.2.4. Общерекурсивные функции {21}
1.3. Тезис Черча {22}
1.4. Машина Тьюринга {23}
1.4.1. Устройство машины Тьюринга {23}
1.4.2. Вычисление функций на машине Тьюринга {25}
1.4.3. Тезис Тьюринга {26}
1.4.4. Универсальная машина Тьюринга {27}
1.5. Два типа вычислимости {27}
1.5.1. Вычислимые функции первого типа {27}
1.5.2. Вычислимые функции второго типа {27}
1.6. Вычислимые функции действительного переменного {28}
1.7. Квантовая вычислимость {29}
1.8. Алгоритмы без первого шага {30}
2 Конструктивная математика {31}
2.1. Интуиционизм {32}
2.2. Интуиционизм Канта {34}
2.3. Интуиционистская логика Гейтинга{35}
2.4. Конструктивная математика Маркова {37}
2.4.1. Конструктивные натуральные числа {38}
2.4.2. Потенциальная осуществимость конструктивного процесса. Конструктивные объекты {39}
2.4.3. Конструктивная логика {40}
2.4.4. Конструктивная теория множеств и топосы реализуемости {41}
2.5. Нормальные алгорифмы Маркова {41}
2.6. Л.Э.Я. Брауэр {43}
2.7. А.А. Марков-младший {44}
3 Реализуемость Клини {46}
3.1. Гeделевская нумерация и индексы функций {47}
3.1.1. Гeделевские номера{47}
3.1.2. Представление частично рекурсивных функций. Индексы {49}
3.2. Рекурсивная реализуемость {50}
3.3. Формальная теория и ее классическая интерпретация {52}
3.3.1. Определение формальной теории {52}
3.3.2. Интерпретация формальной теории {53}
3.4. Формальная арифметика {54}
3.4.1. Интерпретации формальной арифметики {56}
3.4.2. Рекурсивная интерпретация арифметики {57}
3.5. С.К. Клини {58}
4 Категории и топосы {59}
4.1. Категории {59}
4.2. Диаграммы {61}
4.2.1. Конечно полные категории {61}
4.2.2. Декартов квадрат. Обратный образ {62}
4.2.3. Морфизмы. Подобъекты {63}
4.2.4. Конечный и начальный объекты {64}
4.3. Функторы {65}
4.4. Категория функторов E^ K {66}
4.5. Топосы {67}
4.5.1. Произведение объектов и морфизмов {68}
4.5.2. Экспоненциал {69}
4.5.3.}Классификатор}{70}
4.5.4. Определение топоса {71}
4.6. Логика топоса {72}
4.6.1. Алгебра подобъектов и ее логика {72}
4.6.2. Категория Sub(D) {73}
4.6.3. Функтор обратного образа f^{-1} {73}
4.6.4. Логические связки в топосе {74}
4.7. Интерпретации в топосах формальных языков 1-го порядка {75}
4.8. Вложение Ионеды {79}
4.9. Топос пучков {80}
4.9.1. Топология Гротендика {80}
4.9.2. Категории предпучков и пучков {81}
4.9.3. Топосы Гротендика {84}
4.10. Пополнение категорий {84}
4.10.1. Отношения эквивалентности на объектах. Фактор-объекты {84}
4.10.2. Регулярная категория {86}
4.10.3. Точное пополнение категорий {86}
4.11. Геометрический морфизм между топосами {88}
4.11.1. Сопряжение функторов {88}
4.11.2. Определения геометрического морфизма {89}
4.12. Кванторы {89}
4.13. Числовые объекты {91}
4.13.1. Объект натуральных чисел {91}
4.13.2. Объект целых чисел {92}
4.13.3. Объект рациональных чисел {95}
4.14. Внутренняя логика топоса. Язык Митчела—Бенабу {95}
4.14.1. Описания языка Митчела—Бенабу {96}
4.14.2. Интерпретация внутреннего логического языка Митчела—Бенабу {97}
4.15. Объект действительных чисел {100}
4.16. У. Ловер {101}
4.17. А. Гротендик {102}
5 Эффективный топос {103}
5.1. Объекты топоса Eff {104}
5.2. Морфизмы топоса Eff {105}
5.3. Конечные произведения {105}
5.4. Экспоненциал {106}
5.5. Классификатор {106}
5.6.Объект натуральных чисел {107}
5.7. Объект действительных чисел {108}
5.8. Интерпретация конструктивных логики и арифметики с помощью эффективного топоса {109}
5.9. Вычислимость в топосе Eff {109}
5.10. Дж.М. Хайлэнд {110}
6 Топосы реализуемости над частичными комбинаторными алгебрами {111}
6.1. Алгебры Шейнфинкеля {113}
6.1.1. Нумералы и рекурсия в рса {114}
6.1.2. Морфизмы pca {115}
6.2. Категория аcсамблей Ass(A) {115}
6.3. Денотационная семантика {116}
6.4. Топос реализуемости RT(A) {117}
6.4.1. Стандартные топосы реализуемости {118}
6.4.2. Топос Eff как топос реализуемости {118}
6.5. М.Э. Шейнфинкель {119}
7 Топосы пучков над алгебрами Шейнфинкеля {121}
7.1. Категория умеренных множеств {121}
7.1.1. Категория Mod(A) {121}
7.1.2. Категория A {123}
7.2. Топосы пучков над pca A {123}
7.3. Диаграмма для категорий Mod(A), Ass(A), RT(A) и Sh_C(A) {124}
7.4. Категория частичных отношений эквивалентности PER(A) {125}
7.5. Реализуемость и модели вычислимости {126}
8 Рекурсивный топос {128}
8.1. Категория нумерованных множеств Ершова {128}
8.1.1. Нумерации множества и его подмножеств {128}
8.1.2. Категория Ершова En {129}
8.2. Рекурсивный топос Малри {130}
8.3. Категория эффективных доменов Скотта Edom {131}
8.3.1. Топология Скотта {132}
8.3.2. Эффективный домен Скотта {133}
8.3.3. Категория Edom {133}
8.3.4. Синтетическая теория доменов {134}
8.4. Применение теории нумераций в программировании {134}
8.5. Ю.Л. Ершов {136}
8.6. Ф. Малри {137}
8.7. Д. Скотт {138}
Заключение ...........................................140
Литература ........................................... 143
Предметный указатель ........................................ 149