Máquina de Turing multipista

Las máquinas Turing multipista, un tipo específico de máquina Turing multipista, contienen varias pistas, pero solo un cabezal de cinta lee y escribe en todas las pistas. Aquí, un solo cabezal de cinta lee n símbolos denpistas en un solo paso. Acepta lenguajes recursivamente enumerables como acepta una máquina Turing de una sola cinta de una sola pista normal.

Una máquina de Turing multipista se puede describir formalmente como una tupla de 6 (Q, X, ∑, δ, q 0 , F) donde -

  • Q es un conjunto finito de estados

  • X es el alfabeto de la cinta

  • es el alfabeto de entrada

  • δ es una relación de estados y símbolos donde

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

  • q0 es el estado inicial

  • F es el conjunto de estados finales

Note - Para cada máquina de Turing de una sola pista S, hay una máquina de Turing multipista equivalente M tal que L(S) = L(M).