Машина Тьюринга

Лабораторная работа № 5.

МАШИНА ТЬЮРИНГА И РЕКУРСИВНЫЕ ФУНКЦИИ

Машина Тьюринга

Машина Тьюринга – абстрактное устройство, состоящее из бесконечной в обе стороны ленты, считывающей и печатающей головки, способной перемещаться вправо и влево, и управляющего устройства. Лента разбита на ячейки. В ячейках могут быть записаны символы некоторого конечного алфавита

Команда расшифровывается так: если машина находится в состоянии q и считанный с ленты символ a, то машина переходит в состояние q’, печатает в текущей клетке символ a’ и затем выполняет одно из трех действий D. Изначально машина находится в состоянии q1. Если машина пришла в состояние q0, то она останавливается. Машина называется применимой к некоторой записи на ленте, если при работе над этой записью после конечного числа шагов она останавливается. Если она никогда не остановится, то машина называется неприменимой к этой записи. Машину Тьюринга удобно применять при вычислении функций вида