Machine de Turing multipiste

Les machines de Turing multi-pistes, un type spécifique de machine de Turing multi-bandes, contiennent plusieurs pistes, mais une seule tête de bande lit et écrit sur toutes les pistes. Ici, une seule tête de bande lit n symboles denpistes en une seule étape. Il accepte des langages récursivement énumérables comme l'accepte une machine normale à bande unique à une seule piste de Turing.

Une machine de Turing multipiste peut être formellement décrite comme un 6-tuple (Q, X, ∑, δ, q ₀ , F) où -

• Q est un ensemble fini d'états

• X est l'alphabet de la bande

• ∑ est l'alphabet d'entrée

• δ est une relation sur les états et les symboles où

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

• q₀ est l'état initial

• F est l'ensemble des états finaux

Note - Pour chaque machine de Turing à voie unique S, il existe une machine de Turing multi-pistes équivalente M tel que L(S) = L(M).