Верещагин, Шень. Вычислимые функции.

1. Предисловие
1. Вычислимость, разрешимость и перечислимость
   • Вычислимые функции
   • Разрешимые множества
   • Перечислимые множества
   • Перечислимые и разрешимые множества
   • Перечислимость и разрешимость
2. Универсальные функции и неразрешимость
   • Универсальные функции
   • Диагональная конструкция
   • Перечислимое неразрешимое множество
   • Перечислимые неотделимые множества
   • Простые множества: конструкция Поста
3. Нумерации и операции
   • Главные универсальные функции
   • Вычислимые последовательности функций
   • Главные универсальные множества
4. Свойства главных нумераций
   • Множество номеров
   • Новые номера старых функций
   • Изоморфизм главных нумераций
   • Перечислимые свойства функций
5. Теорема о неподвижной точке
   • Неподвижная точка и отношения эквивалентности
   • Программа, печатающая свой текст
   • Системный трюк: ещё одно доказательство
   • Несколько замечаний
6. m-сводимость и свойства перечислимых множеств
   • m-сводимость
   • m-полные множества
   • m-полнота и эффективная неперечислимость
   • Изоморфизм m-полных множеств
   • Продуктивные множества
   • Пары неотделимых множеств
7. Вычисления с оракулом
   • Машины с оракулом
   • Эквивалентное описание
   • Релятивизация
   • 0'-вычисления
   • Несравнимые множества
   • Теорема Мучника--Фридберга: схема конструкции
   • Теорема Мучника--Фридберга: выигрышные условия
   • Теорема Мучника--Фридберга: метод приоритета
8. Арифметическая иерархия
   • Классы \Sigma_n и \Pi_n
   • Универсальные множества в \Sigma_n и \Pi_n
   • Операция скачка
   • Классификация множеств в иерархии
9. Машины Тьюринга
   • Зачем нужны простые вычислительные модели?
   • Машины Тьюринга: определение
   • Машины Тьюринга: обсуждение
   • Ассоциативные исчисления
   • Двусторонние исчисления
   • Полугруппы, образующие и соотношения
10. Арифметичность вычислимых функций
    • Программы с конечным числом переменных
    • Машины Тьюринга и программы
    • Арифметичность вычислимых функций
    • Теоремы Тарского и Гёделя
    • Прямое доказательство теорем Тарского и Гёделя
    • Арифметическая иерархия и перемены кванторов
11. Рекурсивные функции
    • Примитивно рекурсивные функции
    • Примеры примитивно рекурсивных функций
    • Примитивно рекурсивные множества
    • Другие виды рекурсии
    • Машины Тьюринга и рекурсивные функции
    • Частично рекурсивные функции
    • Вычислимость с оракулом
    • Оценки скорости роста. Функция Аккермана
1. Литература