Máquina de Turing Multi-track
As máquinas de Turing com várias trilhas, um tipo específico de máquina de Turing com várias fitas, contêm várias trilhas, mas apenas um cabeçote de fita lê e grava em todas as trilhas. Aqui, uma única cabeça de fita lê n símbolos denfaixas em uma etapa. Ele aceita linguagens recursivamente enumeráveis como uma Turing Machine de uma única faixa normal aceita.
Uma máquina de Turing Multi-track pode ser formalmente descrita como uma 6-tupla (Q, X, ∑, δ, q 0 , F) onde -
Q é um conjunto finito de estados
X é o alfabeto da fita
∑ é o alfabeto de entrada
δ é uma relação sobre estados e símbolos onde
δ (Q i , [a 1 , a 2 , a 3 , ....]) = (Q j , [b 1 , b 2 , b 3 , ....], Left_shift ou Right_shift)
q0 é o estado inicial
F é o conjunto de estados finais
Note - Para cada máquina de Turing de pista única S, há uma Máquina de Turing multitrilha equivalente M de tal modo que L(S) = L(M).