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

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

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

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

3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1}), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, «конструктивные объекты». Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.

Оглавление
Предисловие
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. Изоморфизм главных нумераций
4.5. Перечислимые свойства функций
5. Теорема о неподвижной точке
5.1. Неподвижная точка и отношения эквивалентности
5.2. Программа, печатающая свой текст
5.3. Системный трюк: ещё одно доказательство
5.4. Несколько замечаний
6. m-сводимость и свойства перечислимых множеств
6.1. m-сводимость
6.2. m-полные множества
6.3. m-полнота и эффективная неперечислимость
6.4. Изоморфизм неполных множеств
6.5. Продуктивные множества
6.6. Пары неотделимых множеств
7. Вычисления с оракулом
7.1. Машины с оракулом
7.2. Эквивалентное описание
7.3. Релятивизация
7.4. 0' - вычисления
7.5. Несравнимые множества
7.6. Теорема Мучника Фридберга: общая схема
7.7. Теорема Мучника Фридберга: выигрышные условия
7.8. Теорема Мучника Фридберга: метод приоритета
7.9. Решётка Медведева
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, Вычислимые функции, Верещагин Н.К., Шень А., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

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


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

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