Назад (Информатика).

Абстрактная машина Тьюринга

Машина Тьюринга состоит из информационной ленты, каретки [считывающая и записывающая головка], лентопротяжного механизма и операционного исполнительного устройства.

Лента ограничена [т.е. жестко закреплена] слева и бесконечна справа. Лента разделена на секции одинакового размера.

В каждую секцию ленты заносятся символы внешнего алфавита машины Тьюринга A = {a0, a1,... aN}, где а0, как правило, пробел.

Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной секции ленты; говорят, что каретка обозревает эту секцию. А такая секция называется текущей или обозреваемой.

За единицу времени, которая называется шагом, каретка может сдвинуться на одну секцию влево или вправо. Кроме того, каретка может также распознать содержимое обозреваемой секции, может заносить символ внешнего алфавита в текущую секцию и может стирать содержимое текущей ячейки.

Операционное исполнительное устройство может находиться в одном из дискретных состояний: Q = {q0, q1,...qM} - внутренний алфавит машины Тьюринга или алфавит внутренних состояний.

Система команд машины Тьюринга

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

A/QQ0Q1...Qn
A0
A1
...
Am

Пример программы инвертирования двоичных чисел для машины Тьюринга

A/QQ0Q1
01 >Q11 >Q1
10 >Q10 >Q1
__ >Q0_ !Q1