Многоленточная машина Тьюринга

Многоленты Машины Тьюринга имеют несколько лент, доступ к каждой из которых осуществляется с отдельной головки. Каждая голова может двигаться независимо от других голов. Первоначально вход находится на ленте 1, а остальные пустые. Сначала первая лента занята входом, а остальные ленты остаются пустыми. Затем машина считывает последовательные символы под своими головами, а TM печатает символ на каждой ленте и перемещает ее головки.

Многоленточную машину Тьюринга можно формально описать как набор из 6 (Q, X, B, δ, q ₀ , F), где -

• Q конечный набор состояний

• X ленточный алфавит

• B это пустой символ

• δ отношение состояний и символов, где

  δ: Q × X ^k → Q × (X × {Left_shift, Right_shift, No_shift}) ^k

  где есть k количество лент

• q₀ это начальное состояние

• F это набор конечных состояний

Note - Каждая многоленточная машина Тьюринга имеет эквивалентную однопленочную машину Тьюринга.