Многодорожечная машина Тьюринга

Многоканальные машины Тьюринга, особый тип многоканальной машины Тьюринга, содержат несколько дорожек, но только одна ленточная головка считывает и записывает все дорожки. Здесь одна головка ленты считывает n символов из n дорожек за один шаг. Он принимает рекурсивно перечислимые языки, как это допускает обычная одноленточная одноленточная машина Turing.

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

• Q — конечное множество состояний

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

• ∑ является входным алфавитом

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

  δ (Q _i , [a ₁ , a ₂ , a ₃ , ….]) = (Q _j , [b ₁ , b ₂ , b ₃ , ….], Left_shift или Right_shift)

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

• F — множество конечных состояний

Q — конечное множество состояний

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

∑ является входным алфавитом

δ — отношение к состояниям и символам, где

δ (Q _i , [a ₁ , a ₂ , a ₃ , ….]) = (Q _j , [b ₁ , b ₂ , b ₃ , ….], Left_shift или Right_shift)

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

F — множество конечных состояний

Примечание. Для каждой машины Тьюринга S с одной дорожкой существует эквивалентная машина Тьюринга с несколькими дорожками, такая, что L (S) = L (M) .