Рассмотрим устройство, которое состоит из бесконечной в оба конца ленты и автомата. Лента разбита на ячейки, в которые вписываются символы из алфавита {0, 1, ..., N-1}, причем символ "0" означает также и пустой символ. Автомат может находиться в одном из состояний {q₁, ..., q_r} и осуществлять одно из трех движений в каждый момент времени, {R, L, S}: R - переместиться на одну ячейку вправо, L - переместиться на одну ячейку влево, S - остаться на месте. Работу такого устройства можно задать с помощью специальной таблицы, называемой программой.

В самом левом столбце располагаются символы алфавита {0, 1, ..., N-1} (внешний алфавит машины). Множество {q1, ..., qr} - внутренний алфавит машины. Некоторые клетки этой таблицы могут быть пустыми. В клетки этой таблицы записываются команды машины, т.е. тройки символов cDq, где c - символ из внешнего алфавита машины, q - символ из внутреннего алфавита машины и D - символ из алфавита, описывающего движение, т.е. из множества {R, L, S}.

Если в некоторый момент времени головка автомата обозревает на ленте символ a и автомат находится в состоянии q_i, то машина должна выполнить команду, стоящую на пересечении строки с номером a и столбца с номером q_i. Если в означенной клетке находится команда cDq, то машина должна записать в текущую ячейку символ c, перейти в состояние q и осуществить движение D. Если означенная клетка окажется пустой, то машина останавливается. Считается, что в начальный момент обозревается начальная клетка и автомат находится в состоянии q₁. В результате применения программы возможны 2 ситуации:

1. В некоторый момент времени появится пустая команда (или пустая клетка) и машина остановится.
2. Пустая клетка никогда не появится и машина не остановится.