Программа для машины Тьюринга

Такт работы машины Тьюринга

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

1) записывает некоторый символ S′ в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется);

2) сдвигается на одну клетку влево (обозначение – L, от left), либо на одну клетку вправо (обозначение – R, от right), либо остается неподвижным (обозначение – N).

3) переходит в некоторое состояние q′ (в частности, может остаться в прежнем состоянии).

Формально действия одного такта будем записывать в виде тройки:

S′, [L,R,N], q′,

где конструкция с квадратными скобками означает возможность записи в этом месте любой из букв L, R или N. Например, такт *,L,q8 означает запись символа * в видимую клетку, сдвиг на одну клетку влево и переход в состояние q8.

Сама по себе МТ ничего не делает. Для того чтобы заставить её работать, надо написать для неё программу. Эта программа записывается в виде следующей таблицы:

Слева перечисляются все состояния, в которых может находиться автомат, сверху – все символы (в том числе и Λ), которые автомат может видеть на ленте. (Какие именно символы и состояния указывать в таблице – определяет автор программы.) На пересечениях же (в ячейках таблицы) указываются те такты, которые должен выполнить автомат, когда он находится в соответствующем состоянии и видит на ленте соответствующий символ.

В целом таблица определяет действия МТ при всех возможных конфигурациях и тем самым полностью задаёт поведение МТ. Описать алгоритм в виде МТ – значит предъявить такую таблицу.

Примечание – Часто МТ определяют как состоящую из ленты, автомата и программы, поэтому при разных программах получаются разные МТ. Мы же будет считать, в духе современных компьютеров, что МТ одна, но она может выполнять разные программы.