Машина Тьюринга відрізняється від машини Поста тим, що алфавіт може мати більше двох символів. Взагалі перелік операцій може бути розширений. Наприклад, додати команди зміни змісту комірки перед просуванням стрічки пам’яті (стандартна машина Тьюринга). Тобто будь-яка команда машини Тьюринга може бути представлена як послідовність команд машини Поста.
Нехай алфавіт машини Тьюринга А = (S0, S1, ..., Sn), де S0 = Æ; сукупність станів — це множина Q = {q0, q1, ..., qm},
де q0 — заключний стан;
А — зовнішній алфавіт машини;
Q — внутрішній алфавіт.
У кожний момент часу машина має певну послідовність станів комірок та 1 стан керуючого пристрою, а зчитувальна головка знаходиться навпроти якоїсь комірки. Сукупність усіх елементів, що визначають стан машини, називають конфігурацією машини.
Наприклад:
qi
|
| S0
| Sj
| Sj
| Sj
| ...
|
|
| Sj
|
|
|
|
| Sj
| Sj
| S0
|
1 2 3 ... ... ... k ... ... ... ... r-1 r
Конфігурація машини у вигляді слова:
... S0 Sj1 Sj2 Sj3 ... qj Sjk ... Sjr-1 Sjr S0 ... ,
де S0 — пуста комірка,
Sj1 — стан (зміст) першої непустої лівої комірки;
Sjk — стан комірки, що розглядається у даний момент часу;
r — кількість зайнятих комірок;
qi — стан керуючого пристрою; i = 0,1 … m.
Якщо машина перебуває у стані qі , має доступ до комірки із символом sk , переходить у стан qj , замінюючи символ sk на sm, a стрічка пересувається ліворуч на одну комірку, то це означає, що вона виконує команду
qi sk ® qj sm Л або qi sk qi sm Л.
Замість Л можуть стояти П або С:
де Л — рух стрічки ліворуч;
П — рух стрічки праворуч;
С — стрічка не рухається.
Отже, перехід від однієї до іншої конфігурації здійснюється за допомогою команди. Загальний вигляд команди
qi sk ® qj sm T ,
де T = Л, П, С.
Сукупність усіх команд машини називають її програмою.
Щоб задати машину Тьюринга, треба задати її внутрішній та зовнішній алфавіт, програму, початкову конфігурацію, якими символами позначені пуста комірка та заключний стан керуючого пристрою.
Програму машини Тьюринга можна задати у вигляді таблиці.
Наприклад, задано таблицю:
 А
Q
|
|
| *
| S0
|
| q2
| —
| q2 0 Л
| q1*Л
| q0C
|
| q1
| q21Л
| —
| —
| —
|
| q0
| останов
|
|
|
|
Машина Тьюринга, представлена цією таблицею, здійснює перетворення слова 1*0 у слово 0*1. Наведемо алгоритм переносу 0 разом зі зміною конфігурацій після виконання кожної команди.
Нехай початкова конфігурація машини має вигляд: s0 q2 1* 0 s0. Тоді:
q1 1 ® q2 0 Л s0 0 q2 * 0 s0
q2 * ® q1 * Л s0 0 * q1 0 s0
q1 0 ® q1 1 Л s0 0 * 1 q2 s0
q2 s0 ® q0 s0 C s0 0 * 1 q0 s0 — заключна
конфігурація машини.
З часом з’явилися різні модифікації машини Тьюринга залежно від кількості використовуваних стрічок пам’яті, кількості станів керуючого пристрою. Так, існує машина Тьюринга з двома виходами. Якщо додати у керуючий пристрій певний стан q*, то: якщо керуючий пристрій переходить у стан q0 для заданого вхідного слова Х, то машина допускає Х; якщо керуючий пристрій переходить у стан q*, то машина забороняє стан Х.
Багатострічкова машина Тьюринга має декілька стрічок, поділених на комірки. В кожній комірці може знаходитись один із символів зовнішнього алфавіту А. Керуючий пристрій може знаходитись в одному зі станів Q = {q0, q1 ... qm}, де q0 — заключний стан. Конфігурація машини вважається заданою, якщо відомий стан керуючого пристрою, стан всіх комірок, всіх стрічок та вказані комірки, що доступні на даний момент зчитувальним головкам. Конфігурація складається з К слів, якщо машина має К стрічок пам’яті.
