Macchina di Turing multi-nastro

Le macchine di Turing multi-nastro hanno più nastri in cui si accede a ciascun nastro con una testina separata. Ogni testa può muoversi indipendentemente dalle altre teste. Inizialmente l'ingresso è sul nastro 1 e gli altri sono vuoti. All'inizio, il primo nastro è occupato dall'ingresso e gli altri nastri vengono lasciati vuoti. Successivamente, la macchina legge simboli consecutivi sotto le sue teste e il TM stampa un simbolo su ogni nastro e muove le sue teste.

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

• Q è un insieme finito di stati

• X è l'alfabeto del nastro

• B è il simbolo vuoto

• δ è una relazione su stati e simboli dove

  δ: Q × X ^k → Q × (X × {Shift_sinistra, Shift_Destra, No_shift}) ^k

  dove c'è k numero di nastri

• q₀ è lo stato iniziale

• F è l'insieme degli stati finali

Note - Ogni macchina di Turing Multi-nastro ha una macchina di Turing a nastro singolo equivalente.