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 0 , 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 1 , a 2 , a 3 , ....]) = (Q j , [b 1 , b 2 , b 3 , ....], Left_shift ou Right_shift)
q0 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).