Машина Тьюринга () имеет конечное число знаков si, образующих внешний алфавит, в котором кодируются сведения, подаваемыев МТ, а также вырабатываемые в ней. Среди знаков имеется пустой знак (s1), посылка которого в какую-либо ячейку стирает находившийся в ней знак и оставляет ее пустой.
В зависимости от поданной начальной информации α (содержащихся на ленте внешней памяти знаков) возможны два случая:
В каждый момент обозревается лишь одна ячейка ленты (памяти). Переход может осуществляться лишь к соседней ячейке ( r - вправо, l-влево, n- нет перехода (остаться)). Переход к произвольной ячейке производится путем последовательного перебора всех ячеек, разделяющих текущую и необходимую ячейки. На каждом отдельном такте t команда предписывает только замену единственного знака si, хранящегося в обозреваемой ячейке, каким-либо другим знаком sj.
Логический блок МТ имеет конечное число состояний {qi} i=1..m.
Знаки r, l, n, q1,..,qmобразуют внутренний алфавит машины.
Переработанный знак sj, записываемый в просматриваемую ячейку, состояние, которое примет машина Тьюринга в следующем такте q(t+1) и выполняемая в данном такте операция перехода к следующей ячейке p(t+1) являются функцией анализируемого в данном такте символа и текущего состояния машины si и q(t):
si(t+1)=f1(si,q(t)); q(t+1)=f2(si,q(t)); P(t+1)=f3(si,q(t)).Программа для МТ определяется тройкой {si, P, q}t.
Пример записи программы вычисления логической функции "неравнозначность" для машины Тьюринга представлен ниже.
0 | 0, r, q1 | 0, n, q4 | 1, n, q4 | 0, n, q4 |
1 | 1, r, q3 | 1, n, q4 | 0, n, q4 | 1, n, q4 |
Перед началом работы машина Тьюринга находится в состоянии q1 считывания первого операнда.