Шоломов Л.А.; Емельянов С.В. (ред.). Основы теории дискретных устройств. Раздел: Теория алгоритмов

Курс лекций. — М.: МИСиС, 1977. — 127 с.Излагаемый курс преследует две цели. С одной стороны, рассматриваются принципиальные вопросы, связанные с вычислениями, не зависящие от конкретной концепции машины. К ним относятся, например, следующие. Всякая ли задача может быть решена на машине (при наличии неограниченного ресурса памяти и времени), что такое "универсальная машина" и какие задачи она может решать, сколь "сложным" может быть решение задачи, можно ли извлечь из программы информацию о решаемой задаче и др. С другой стороны, в курсе излагаются методы доказательства алгоритмической неразрешимости задач. Такие задачи встречаются, в частности, в кибернетике. В качестве примера приводится доказательство алгоритмической неразрешимости проблемы полноты конечной системы автоматов.Введение.
Машины Тьюринга.
Основные понятия, связанные с машинами Тьюринга.
Тьюрингово программирование.
Пример алгоритмически неразрешимой проблемы.
Частично-рекурсивные функции.
Понятие частично-рекурсивной функции.
Доказательство рекурсивности некоторых употребительных функций.
Нумерационные функции и их применение.
Эквивалентность моделей алгоритмов.
Вычисление частично-рекурсивных функций на машинах Тьюринга.
Частичная рекурсивность функций, вычисленных на машинах Тьюринга.
Универсальные машины и универсальные функции.
Универсальная машина Тьюринга.
Универсальная частично-рекурсивная функция.
Некоторые общие теоремы теории алгоритмов.
Алгоритмические неразрешимые проблемы.
Неразрешимость некоторых массовых проблем.
Неразрешимость проблемы полноты конечной системы автоматов.
Сложность вычислений.
Сложно-вычислимые функции.
Нижние оценки сложности вычислений.
Литература.