Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач

Уч-метод. пособие — М.: ВМК МГУ, 2006. — 47 с.Задачи на составление алгоритмов в виде машины Тьюринга и нормальных алгоритмов Маркова, а также задачи теоретического характера.
Сведения по теории алгоритмов, типичные приёмы решения задач и большой набор задач для самостоятельного решения.
Пособие рассчитано на студентов 1 курса факультета ВМК МГУ и преподавателей, ведущих семинарские занятия по программированию.Содержание:
Машина Тьюринга.
Краткое описание машины Тьюринга.
Примеры на составление программ для МТ.
Задачи для самостоятельного решения.
Нормальные алгоритмы Маркова.
Краткое описание нормальных алгоритмов Маркова.
Примеры на составление НАМ.
Задачи для самостоятельного решения.
Задачи теоретического характера.
Применимость алгоритма.
Самоприменимость алгоритма.
Эквивалентность алгоритмов.
Композиция алгоритмов.
Задачи для самостоятельного решения.