А.К.Гуц

СИНТЕТИЧЕСКАЯ
ВЫЧИСЛИМОСТЬ

Омск: Изд-во ОмГУ, 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