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).