Синтетическая вычислимость, Гуц А.К., 2016

Синтетическая вычислимость, Гуц А.К., 2016.
 
   Излагаются элементы современной теории синтетической вычислимости. Дается представление об алгоритмах, рекурсивных функциях, интуиционизме, интуиционистской логике, конструктивной математике, реализуемости Клини, теории категорий, теории топосов, топосе реализуемости и др. Описываются эффективный топос Хайлэнда и рекурсивный топос Малри, в которых все функции f:N→N и f:Nn→N соответственно вычислимы.
Для студентов и аспирантов факультетов компьютерных наук, информационных технологий и математических факультетов.




Конструктивная математика Маркова.
Основная цель конструктивной математики - избавиться от традиционных для классической математики неэффективных методов, посредством которых доказывается существование того или иного объекта с заданным свойством, но при этом не показывается, как такой объект с этим свойством может быть построен.

Критика неэффективных методов, которые допускаются в классической математике, привела Бауэра к тому, что он явно указал, что неэффективные методы появляются отчасти от того, что классическая математика базируется на классической двузначной логике, одной их аксиом которой является закон исключенного третьего. В пределах логики высказываний закон исключенного третьего - это единственный неэффективный логический принцип [37, с. 49]. Брауэр предложил отказаться от использования этого закона. Как результат, возникла интуиционистская логика, формализованную теорию которой первым построил Гейтинг [71]. Она содержит логические принципы конструктивистской математики.

ОГЛАВЛЕНИЕ.
Введение.
1. Вычислимость и алгоритмы.
1.1. Интуитивное определение алгоритма и вычислимой функции.
1.1.1. Определение алгоритма.
1.1.2. Определение вычислимой функции. 
1.2. Рекурсивные функции Эрбрана-Гёделя-Клини.
1.2.1. Примитивно рекурсивные функции. 
1.2.2. Рекурсия и противоречивость теории.
1.2.3. Частично рекурсивные функции.
1.2.4. Общерекурсивные функции.
1.3. Тезис Чёрча.
1.4. Машина Тьюринга.
1.4.1. Устройство машины Тьюринга.
1.4.2. Вычисление функций на машине Тьюринга.
1.4.3. Тезис Тьюринга.
1.4.4. Универсальная машина Тьюринга. 
1.5. Два типа вычислимости.
1.5.1. Вычислимые функции первого типа.
1.5.2. Вычислимые функции второго типа.
1.6. Вычислимые функции действительного переменного.
1.7. Квантовая вычислимость.
1.8. Алгоритмы без первого шага.
2. Конструктивная математика.
2.1. Интуиционизм.
2.2. Интуиционизм Канта.
2.3. Интуиционистская логика Рейтинга.
2.4. Конструктивная математика Маркова.
2.4.1. Конструктивные натуральные числа.
2.4.2. Потенциальная осуществимость конструктивного процесса. Конструктивные объекты.
2.4.3. Конструктивная логика.
2.4.4. Конструктивная теория множеств и топосы реализуемости.
2.5. Нормальные алгорифмы Маркова.
2.6. Л.Э.Я. Брауэр.
2.7. А.А. Марков-младший.
3. Реализуемость Клини.
3.1. Гёделевская нумерация и индексы функций.
3.1.1. Гёделевские номера.
3.1.2. Представление частично рекурсивных функций. Индексы.
3.2. Рекурсивная реализуемость.
3.3. Формальная теория и ее классическая интерпретация.
3.3.1. Определение формальной теории.
3.3.2. Интерпретация формальной теории.
3.4. Формальная арифметика.
3.4.1. Интерпретации формальной арифметики.
3.4.2. Рекурсивная интерпретация арифметики.
3.5. С.К. Клини.
4. Категории и топосы.
4.1. Категории.
4.2. Диаграммы.
4.2.1. Конечно полные категории.
4.2.2. Декартов квадрат. Обратный образ. 
4.2.3. Морфизмы. Подобъекты.
4.2.4. Конечный и начальный объекты.
4.3. Функторы.
4.4. Категория функторов Ɛк.
4.5. Топосы.
4.5.1. Произведение объектов и морфизмов.
4.5.2. Экспоненциал.
4.5.3. Классификатор.
4.5.4. Определение топоса.
4.6. Логика топоса.
4.6.1. Алгебра подобъектов и ее логика.
4.6.2. Категория Sub(D).
4.6.3. Функтор обратного образа f-1.
4.6.4. Логические связки в топосе.
4.7. Интерпретации в топосах формальных языков 1-го порядка.
4.8. Вложение Ионеды.
4.9. Топос пучков.
4.9.1. Топология Гротендика.
4.9.2. Категории предпучков и пучков.
4.9.3. Топосы Гротендика.
4.10. Пополнение категорий.
4.10.1. Отношения эквивалентности на объектах. Фактор-объекты.
4.10.2. Регулярная категория.
4.10.3. Точное пополнение категорий.
4.11. Геометрический морфизм между топосами.
4.11.1. Сопряжение функторов.
4.11.2. Определения геометрического морфизма.
4.12. Кванторы.
4.13. Числовые объекты.
4.13.1. Объект натуральных чисел.
4.13.2. Объект целых чисел.
4.13.3. Объект рациональных чисел.
4.14. Внутренняя логика топоса. Язык Митчела-Бенабу.
4.14.1. Описания языка Митчела-Бенабу.
4.14.2. Интерпретация внутреннего логического языка Митчела-Бенабу.
4.15. Объект действительных чисел.
4.16. У. Ловер.
4.17. А. Гротендик.
5. Эффективный топос.
5.1. Объекты топоса Ɛff.
5.2. Морфизмы топоса Ɛff.
5.3. Конечные произведения.
5.4. Экспоненциал.
5.5. Классификатор.
5.6. Объект натуральных чисел.
5.7. Объект действительных чисел.
5.8. Интерпретация конструктивных логики и арифметики с помощью эффективного топоса.
5.9. Вычислимость в топосе Ɛff.
5.10. Дж.М. Хайлэнд.
6. Топосы реализуемости над частичными комбинаторными алгебрами.
6.1. Алгебры Шейнфинкеля.
6.1.1. Нумералы и рекурсия в рса.
6.1.2. Морфизмы рса.
6.2. Категория ассамблей Ass(A).
6.3. Денотационная семантика.
6.4. Топос реализуемости RT(A).
6.4.1. Стандартные топосы реализуемости.
6.4.2. Топос Ɛff как топос реализуемости. 
6.5. М.Э. Шейнфинкель.
7. Топосы пучков над алгебрами Шейнфинкеля.
7.1. Категория умеренных множеств.
7.1.1. Категория Mod(A).
7.1.2. Категория (А).
7.2. Топосы пучков над рса А.
7.3. Диаграмма для категорий (А), Mod(A) Ass(A), RT(A) и Shc(A).
7.4. Категория частичных отношений эквивалентности PER(A).
7.5. Реализуемость и модели вычислимости.
8. Рекурсивный топос.
8.1. Категория нумерованных множеств Ершова.
8.1.1. Нумерации множества и его подмножеств.
8.1.2. Категория Ершова Еп.
8.2. Рекурсивный топос Малри.
8.3. Категория эффективных доменов Скотта EDom.
8.3.1. Топология Скотта.
8.3.2. Эффективный домен Скотта.
8.3.3. Категория EDom.
8.3.4. Синтетическая теория доменов.
8.4. Применение теории нумераций в программировании.
8.5. Ю.Л. Ершов.
8.6. Ф. Малри.
8.7. Д. Скотт.
Заключение.
Литература.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Синтетическая вычислимость, Гуц А.К., 2016 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - djvu - Яндекс.Диск.




Хештеги: #учебник по математике :: #математика :: #Гуц :: #интуиционизм :: #топос