Плиско В.Е. Теория алгоритмов

Никаких данных нет.
Содержание
Основные понятия теории алгоритмов
Машина Тьюринга
Частично-рекурсивные функции
Машина с неограниченными регистрами
МНР-вычислимость частично-рекурсивных функций
Нумерация вычислимых функций
Теорема о параметризации
Универсальная вычислимая функция
Разрешимые и перечислимые множества
Теоремы о разрешимых и перечислимых множествах
Нумерация перечислимых множеств
Неразрешимые алгоритмические проблемы
Теорема Райса
Десятая проблема Гильберта
Индексы разрешимых и конечных множеств
Рекурсивно неотделимые перечислимые множества
Теорема Раиса - Шапиро
Многозначная сводимость
Продуктивные множества
Креативные множества
Простые множества
m-полные перечислимые множества
Язык формальной арифметики
Арифметические множества и функции
Гёделева нумерация арифметических формул
Первая теорема Гёделя о неполноте
Меры сложности вычислений
Теорема о неподвижной точке
Теорема об ускорении
Литература