Учебники

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

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

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

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

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

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

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

    δ (Q i , [a 1 , a 2 , a 3 , ….]) = (Q j , [b 1 , b 2 , b 3 , ….], Left_shift или Right_shift)

  • q 0 – начальное состояние

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

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

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

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

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

δ (Q i , [a 1 , a 2 , a 3 , ….]) = (Q j , [b 1 , b 2 , b 3 , ….], Left_shift или Right_shift)

q 0 – начальное состояние

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

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