Многоленточные машины Тьюринга имеют несколько лент, к которым каждая лента доступна с отдельной головкой. Каждая голова может двигаться независимо от других голов. Первоначально вход находится на ленте 1, а остальные пустые. Сначала первая лента занята вводом, а остальные ленты остаются пустыми. Затем, машина читает последовательные символы под своими головами, и ТМ печатает символ на каждой ленте и перемещает свои головы.
Многоленточная машина Тьюринга может быть формально описана как 6-кортеж (Q, X, B, δ, q 0 , F), где —
-
Q — конечное множество состояний
-
X это ленточный алфавит
-
B — это пустой символ
-
δ — отношение к состояниям и символам, где
δ: Q × X k → Q × (X × {сдвиг влево, сдвиг вправо, сдвиг вправо}) k
где есть k количество лент
-
q 0 — начальное состояние
-
F — множество конечных состояний
Q — конечное множество состояний
X это ленточный алфавит
B — это пустой символ
δ — отношение к состояниям и символам, где
δ: Q × X k → Q × (X × {сдвиг влево, сдвиг вправо, сдвиг вправо}) k
где есть k количество лент
q 0 — начальное состояние
F — множество конечных состояний
Примечание. Каждая многопленочная машина Тьюринга имеет эквивалентную одноленточную машину Тьюринга.