Н.К.Верещагин, А.Шень - Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции
Просмотров: 3190
- Аннотация
- Содержание
- Предисловие
- 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. Оценки скорости роста. Функция Аккермана
- Список литературы
- Предметный указатель
Похожие книги
Билл Флеминг, Даррис Доббс - Методы анимации лица. Мимика и артикуляция
Лидовский В. В. - Теория информации