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

Просмотров: 2059

• Аннотация
• Содержание
• Предисловие
• 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. га-сводимость и свойства перечислимых множеств
• 6.1. т-сводимость
• 6.2. m-полные множества
• 6.3. т-полнота и эффективная неперечислимость
• 6.4. Изоморфизм т-полных множеств
• 6.5. Продуктивные множества
• 6.6. Пары неотделимых множеств
• 7. Вычисления с оракулом
• 7.1. Машины с оракулом
• 7.2. Относительная вычислимость: эквивалентное описание
• 7.3. Релятивизация
• 7.4. О'-вычисления
• 7.5. Несравнимые множества
• 7.6. Теорема Мучника-Фридберга: общая схема конструкции
• 7.7. Теорема Мучника-Фридберга: выигрышные условия
• 7.8. Теорема Мучника-Фридберга: метод приоритета
• 8. Арифметическая иерархия
• 8.1. Классы Е„ и П„
• 8.2. Универсальные множества в Е„ и П„
• 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. Вычислимые функции

Ягуп В. Г. - Конспект лекцій Математичні задачі електроенергетики

Астахова И.Ф. - SQL в примерах и задачах

Разлейцев А. Ф. - Моделирование и оптимизация процессов сгорания в дизелях

В.И.Данилов - Лекции по теория игр