Итак специально для ищущих (а таковые есть) я решил посветить этот пост описанию Машины Тьюринга.
Итак опираясь на текст книги: "Дискретная математика" А.И. Белоусов С.Б. Ткачев давайте посмотрим что же такое - Машина Тьюринга:

Машина Тьюринга - это автомат (автомат Тьюринга).
Определение: Машина Тьюринга определяется кортежем вида
T = (Q,V,*,_,S,L,R,q0,qf,b), где

Q - конечное множество состояний;
V - конечный входной алфавит;
*(не принадлежащая)V - символ, называемый маркером начала ленты;
_(не принадлежащая)V - символ, называемый пустым (или пробелом);
S,L,R(не принадлежащая)V - символы, называемые символами направления движения головки;
q0(принадлежащая)Q - начальное состояние;
qf(принадлежащая)Q - заключительное состояние;
b - функция переходов;

Функция переходов может быть записана в виде системы команд. Каждая команда есть слово вида: qa -> rb,M где

a,b принадлежит V объединенное {*,_}
M принадлежит {S,L,R}
-> не принадлежит V объединенное {*,_,S,L,R}
Слово qa (до стрелки) называется левой частью команды
Слово rb,M (после стрелки) - правой частью команды

Неформально работу машины Тьюринга можно представить следующим образом.
Машина имеет устройство управления, которое может находиться в одном из состояний множества Q, полубесконечную ленту, разделенную на ячейки, в каждой из которых может быть записан символ из алфавита V (объединенный){*,_}, причем крайняя левая ячейка хранит символ *, и головку чтения-записи, которая в каждый момент дискретного времени обозревает какую-то одну ячейку ленты. Символ "_" обозначает пустую ячейку ленты.

Команда "qa -> rb,M" разрешает машине Тьюринга , устройство управления которой находится в состоянии "q", а головка обозревает ячейку, хранящую символ "a", перевести устройство в состояние "r", записав в обозреваемую ячейку символ b (который может и совпадать с "a"), и оставить головку на прежнем месте, если M=S, сдвинуть её на одну ячейку влево, если M=L, или на одну ячейку вправо, если M=R.

-------------------------------------------------------------------------------
Также про машину Тьюринга можно посмотреть в википедии:
http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0....D1.80.D0.B8.D0.BD.D0.B3.D0.B0

При создании данного блога использовалась информация из учебника "Дискретная математика" издательства МГТУ им. Баумана.
Благодарю одно из авторов сей книги, Алексея Ивановича Белоусова.