Macchina di Turing multitraccia

Le macchine di Turing multi-traccia, un tipo specifico di macchine di Turing multi-nastro, contengono più tracce ma solo una testina del nastro legge e scrive su tutte le tracce. Qui, una singola testina del nastro legge n simboli dantracce in un unico passaggio. Accetta linguaggi ricorsivamente enumerabili come una normale macchina di Turing a nastro singolo a traccia singola.

Una macchina di Turing multitraccia può essere formalmente descritta come una tupla di 6 (Q, X, ∑, δ, q ₀ , F) dove -

• Q è un insieme finito di stati

• X è l'alfabeto del nastro

• ∑ è l'alfabeto di input

• δ è una relazione su stati e simboli dove

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

• q₀ è lo stato iniziale

• F è l'insieme degli stati finali

Note - Per ogni macchina di Turing a pista singola S, esiste una macchina di Turing multitraccia equivalente M tale che L(S) = L(M).