Лекции по математической логике и теории алгоритмов, часть 3, Вычислимые функции, Верещагин Н.К., Шонь А., 1999

Лекции по математической логике и теории алгоритмов, Часть 3, Вычислимые функции, Верещагин Н.К., Шонь А., 1999.

  Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В ней рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции). Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся основами теории алгоритмов. Книга включает себя около 90 задач различной трудности.




Вычислимые функции.
Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, её вычисляющий, то есть такой алгоритм А, что
• если f(n) определено для некоторого натурального n, то алгоритм А останавливается на входе п и печатает f(n);
• если f(n) не определено, то алгоритм А не останавливается на входе n.

Несколько замечаний по поводу этого определения:
1. Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определённая функция вычислима (в качестве А надо взять программу, которая всегда зацикливается) .
2. Можно было бы изменить определение, сказав так: «если f(n) не определено, то либо алгоритм А не останавливается, либо останавливается, но ничего не печатает». На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

Оглавление.
Предисловие.
1. Вычислимость, разрешимость и перечислимость.
1.1. Вычислимые функции.
1.2. Разрешимые множества.
1.3. Перечислимые множества.
1.4. Перечислимые и разрешимые множества.
1.5. Перечислимость и вычислимость.
2. Универсальные функции и неразрешимость.
2.1. Универсальные функции.
2.2. Диагональная конструкция.
2.3. Перечислимое неразрешимое множество.
2.4. Перечислимые неотделимые множества.
2.5. Простые множества: конструкция Поста.
3. Нумерации и операции.
3.1. Главные универсальные функции.
3.2. Вычислимые последовательности функций.
3.3. Главные универсальные множества.
4. Свойства главных нумераций.
4.1. Множества номеров.
4.2. Новые номера старых функций.
4.3. Изоморфизм главных нумераций.
4.4. Перечислимые свойства функций.
5. Теорема о неподвижной точке.
5.1. Неподвижная точка и отношения эквивалентности.
5.2. Программа, печатающая свой текст.
5.3. Системный трюк: ещё одно доказательство.
5.4. Несколько замечаний.
6. m-сводимость и свойства перечислимых множеств.
6.1. m-сводимость.
6.2. m-полные множества.
6.3. m-полнота и эффективная неперечислимость.
6.4. Изоморфизм m-полных множеств.
6.5. Продуктивные множества.
6.6. Пары неотделимых множеств.
7. Вычисления с оракулом.
7.1. Машины с оракулом.
7.2. Эквивалентное описание.
7.3. Релятивизация.
7.4. 0'-вычисления.
7.5. Несравнимые множества.
7.6. Теорема Мучника-Фридберга: схема конструкции.
7.7. Теорема Мучника-Фридберга:выигрышные условия.
7.8. Теорема Мучника-Фридберга: метод приоритета.
8. Арифметическая иерархия.
8.1. Классы Еn и Пn.
8.2. Универсальные множества в Σn и Пn.
8.3. Операция скачка.
8.4. Классификация множеств в иерархии.
9. Машины Тьюринга.
9.1. Зачем нужны простые вычислительные модели?.
9.2. Машины Тьюринга: определение.
9.3. Машины Тьюринга: обсуждение.
9.4. Ассоциативные исчисления.
9.5. Моделирование машин Тьюринга.
9.6. Двусторонние исчисления.
9.7. Полугруппы, образующие и соотношения.
10. Арифметичность вычислимых функций.
10.1. Программы с конечным числом переменных.
10.2. Машины Тьюринга и программы.
10.3. Арифметичность вычислимых функций.
10.4. Теоремы Тарского и Гёделя.
10.5. Прямое доказательство теорем Тарского и Гёделя.
10.6. Арифметическая иерархия и перемены кванторов.
11. Рекурсивные функции.
11.1. Примитивно рекурсивные функции.
11.2. Примеры примитивно рекурсивных функций.
11.3. Примитивно рекурсивные множества.
11.4. Другие виды рекурсии.
11.5. Машины Тьюринга и рекурсивные функции.
11.6. Частично рекурсивные функции.
11.7. Вычислимость с оракулом.
11.8. Оценки скорости роста.
Функция Аккермана.
Литература.
Предметный указатель.
Указатель имён.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Лекции по математической логике и теории алгоритмов, часть 3, Вычислимые функции, Верещагин Н.К., Шонь А., 1999 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по математике :: математика :: Верещагин :: Шонь