Основы машины Тьюринга

Машина Тьюринга состоит из управляющего блока, который может считывать и выводить символы на ленту при помощи головки считывания-записи (рис. 11.2). Лента продолжается до бесконечности с обеих сторон машины и разделена на ячейки, каждая из которых может содержать только один символ из конечного набора символов. Этот набор называется машинным алфавитом.

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

Работа машины Тьюринга состоит из последовательности шагов, которые выполняет управляющий блок машины. Каждый шаг заключается в считывании символа из текущей ячейки ленты (то есть ячейки, которую в данный момент просматривает головка считывания-записи), записи символа в эту ячейку, возможно, перемещении головки считывания-записи на одну ячейку влево или вправо и последующей перемене состояния. Действие, которое требуется выполнить, определяется программой, которая отдает приказы управляющему блоку, основываясь на состоянии машины и содержимом текущей ячейки ленты.

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

щую ячейку, которую будем называть текущей ячейкой. Алфавит в нашем примере состоит из символов 0, 1 и *. Лента машины может выглядеть следующим образом:

Считая, что строка символов на ленте обозначает двоичные числа, разделенные звездочками, мы увидим, что на этом отрезке записано значение 5. Наша машина Тьюринга должна увеличивать значение на ленте на 1. Точнее, она считает, что начальная позиция находится на звездочке, которой помечен правый конец строки из нулей и единиц, следовательно, нужно изменить битовую комбинацию слева от звездочки на следующее целое число.