Любые алгоритмы обработки информации

Машина Тьюринга является расширением модели конечного автомата, расширением, включающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу.

Формально машина Тьюринга может быть описана следующим образом. Пусть заданы:
конечное множество состояний – Q, в которых может находиться машина Тьюринга;
конечное множество символов ленты – Г; функция δ (функция переходов или программа),

которая задается отображением пары из декартова произведения Q x Г (машина находится в

состоянии qi и обозревает символ gi) в тройку декартова произведения Q х Г х {L,R} (машина переходит в состояние qi, заменяет символ gi на символ gj и передвигается влево или вправо

на один символ ленты) – Q x Г-->Q х Г х {L,R} один символ из Г-->е (пустой); подмножество

Σ є Г - -> определяется как подмножество входных символов ленты, причем е є (Г - Σ);
одно из состояний – q0 є Q является начальным состоянием машины.

Решаемая проблема задается путем записи конечного количества символов из множества

Σ є Г – Si є Σ на ленту: eS1S2S3S4... ... ... Sne после чего машина переводится в начальное

состояние и головка устанавливается у самого левого непустого символа (q0,­w) –, после чего в соответствии с указанной функцией переходов (qi,Si) - ->(qj,Sk, L или R) машина начинает

заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов. Остановка машины происходит в том случае,

если для пары (qi,Si) функция перехода не определена.

Примеры.