Основные свойства алгоритма дискретности, детерминизма, массовости и результативности позволяют представить процесс вычисления какой-либо числовой функции с помощью математической машины. Эта машина за конечное число шагов позволяет вычислить по исходным данным искомый числовой результат в соответствии с заданными правилами.
Такая модель алгоритма была предложена английским математиком Тьюрингом в конце 30-х годов прошлого столетия, что почти на два десятилетия опередило появление электронных вычислительных машин и послужило их теоретическим прообразом.
Неформальное описание машины Тьюринга
Машина Тьюринга состоит из информационной ленты, считывающей и записывающей головки и управляющего устройства (смотри рисунок 1).
[i125]
Рисунок 1.
Информационная лента бесконечной длины [i126] представляет собой последовательность ячеек, в каждую из которых записан в точности только один символ из множества символов алфавита VT[i127] ={a1, a2,...,an}, иногда называемым внешним алфавитом. Последовательность символов на ленте формирует слово α=(a1 a2,..., a|). Пробел между словами также является символом множества VT[i128]. В дальнейшем такую пустую букву будем обозначать как λ или #. Например, λ (#) 
VT[i129]. В формальных грамматиках множество Vт называют множеством терминальных символов. Информационная лента исполняет функции внешней памяти машины Тьюринга.
Считывающая-записывающая головка [i130] обозревает только одну ячейку информационной ленты, передает информацию о ее содержимом в управляющее устройство, и по указанию последнего сохраняет или изменяет содержимое ячейки. Она способна также передвигаться вправо и влево или оставаться на месте.
Управляющее устройство (внутренняя память) [i131] представляет собой механизм, который на каждом шаге вычисления находится в одном из множества состояний Q = {q1, q2,..., qm}, иногда называемым внутренним алфовитом. В зависимости от состояния qi и считанного символа aj управляющее устройство выдает команду на стирание или запись символа в обозреваемую ячейку, перевод управляющего устройства в новое состояние и перемещение головки на соседнюю ячейку информационной ленты. Поэтому состояния управляющего устройства называют «памятью машины Тьюринга», так как машина помнит все промежуточные состояния, которые привели машину из состояния q0 в состояние qi. С позиции формальных грамматик множество символов, описывающих состояния управляющего устройства, есть множество нетерминальных символов.[i132] Среди всех состояний управляющего устройства следует выделить qo— начальное состояние («старт») и qk — конечное состояние («стоп»), что облегчит составление протоколов машин Тьюринга и композицию нескольких машин Тьюринга. Для описания перемещений головки относительно информационной ленты введем дополнительный алфавит D={П, Л, С}, [i133] где П — означает перемещение головки вправо на одну ячейку информационной ленты, Л — влево на одну ячейку и С — останов. Также часто используют обозначения {L, S, R}, где L(еft) означает «влево», R(ight) – «вправо», a S(top) – «оставаться на месте».
Работа машины Тьюринга состоит в многократном повторении следующего цикла элементарных действий:
-действие первое: считывание символа aj, находящегося под считывающей головкой;
- действие второе: поиск команды, отвечающей текущему состоянию управляющего устройства qi[i134], и считанному символу aj, т.е. qj aj => qi am[i135] D;
- действие третье: исполнение найденной команды, т.е. запись в обозреваемую ячейку символа am, [i136] перевод управляющего устройства в состояние qi и перемещение головки на соседнюю ячейку информационной ленты D.
Эти три действия представляют одну элементарную команду - такт.[i137]
Последовательность команд для реализации процесса вычисления представляют программу алгоритмического процесса или протокол машины Тьюринга. [i138] Следует отметить, что никакие две команды не могут иметь одинаковую пару текущего состояния qi и считываемого символа aj, т.е. пары (qi aj). Машина Тьюринга останавливается только в том случае, если на очередном шаге управляющее устройство генерирует состояние qk. Результатом работы машины Тьюринга будет заключительное слово на информационной ленте.
Может случиться, что в МТ не будет происходить никаких изменений и в другом каком-то состоянии iqi(0.)[i139] В этом случае будем считать, что машина работает «вечно» («зацикливается»).
Конфигурацией на ленте (или состоянием МТ) [i140] называется совокупность образованная:
1) последовательностью a1, a2, …, at символов, записанных в ячейках ленты слева на право без пропусков ячеек. Любая такая последовательность называется, словом в алфавите А;
2) состоянием внутренней памяти qj;
3) номером k воспринимаемой ячейки.
Таким образом, конфигурацию машины записывают в виде машинного слова с указанием ее внутреннего состояния и воспринимаемой ячейки:
a1 … ak-1 
ak+1 … at или a1 a2 … ak-1 qj ak … at
Так как каждая машина имеет конечный алфавит и конечное число внутренних состояний, то из описания ее работы видно, что она может выполнять конечное число различных действий.
Каждая машина Тьюринга определяется своим алфавитом, состоянием внутренней памяти и программой. Для того, чтобы определить работу машины, надо указать ее конфигурацию в начальный момент времени. Для определенности, если это не будет оговорено специально, будем считать, что машина находится во внутреннем состоянии q1[i141], а головка воспринимает самую правую не пустую ячейку.
