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

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

Машина Тьюринга (МТ) состоит из бесконечной в обе стороны ленты и автомата с управляющим устройством. Бесконечная лента разделена на ячейки. Автомат может находиться в одном из состояний . Управляющее устройство в каждый из моментов времени t обозревает одну ячейку ленты. По символу , прочитанному на ленте, и по внутреннему состоянию автомат вырабатывает новое состояние и некоторый символ , который вписывается в ту же ячейку вместо прочитанного. После этого управляющее устройство сдвигается по ленте на одну ячейку вправо или влево или останавливается. Все это делается в соответствии с командой

Рис. 7.1

Таким образом, машина Тьюринга – это пятерка объектов: – внешний алфавит, В – множество внутренних состояний, G: – функция переходов, F: – функция выходов, Н: – функция движения;

Обычно в качестве алфавита берется множество . Машина Тьюринга с произвольным алфавитом допускает моделирование в виде машины с алфавитом . Для ячейки, в которой записан символ 0, будем употреблять термин пустая ячейка. Если лента заполнена сплошь нулями, то будем говорить, что имеем пустую ленту. Совокупность ячеек, которые посетит управляющее устройство, двигаясь от начальной ячейки до обозреваемой в момент t, называется рабочей зоной ленты в момент t.