Исполнитель МТ представляет собой читающую и записывающую головку, которая  может  передвигаться  вдоль  бесконечной  горизонтальной  ленты, разделённой  на  равные  ячейки.  В  каждой  ячейке  находится  ровно  один символ из алфавита исполнителя (множество символов A = {a₀, a₁, …, a_n–1}), включая специальный пустой символ a₀.  

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q =  {q₀,  q₁,  …,  q_n–1}.  В  начальный  момент  времени  головка  находится в начальном состоянии q₀.  

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

Программа работы исполнителя МТ задаётся в табличном виде. 

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении  i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка  обозревает  j-й символ, находясь в i-м  состоянии.  Если  пара «символ – состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент  –  записываемый  в  текущую  ячейку  символ  алфавита  (может совпадать  с  тем,  который  там  уже  записан).  Второй  элемент  –  один  из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг   происходит   после   записи   символа   в   текущую   ячейку.   Третий элемент – новое состояние головки после выполнения команды.  

Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку  записывается  символ  «0»,  затем  головка  сдвигается  в  соседнюю слева ячейку и переходит в состояние q3. 

Приведём пример выполнения программы, заданной таблично.  

На  ленте  записано  неизвестное  ненулевое  количество  расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены  пустым  символом  «λ».  В  начальный  момент  времени  головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z». 

Программа 

заменяет на ленте все символы «Z» на «X» и останавливает исполнителя  в первой ячейке слева от последовательности символов «X».  

Возможное начальное состояние исполнителя: