Machine de Turing multi-bande
Les machines de Turing à bandes multiples ont plusieurs bandes où chaque bande est accessible avec une tête séparée. Chaque tête peut bouger indépendamment des autres têtes. Initialement, l'entrée est sur la bande 1 et les autres sont vierges. Au début, la première bande est occupée par l'entrée et les autres bandes restent vierges. Ensuite, la machine lit les symboles consécutifs sous ses têtes et le TM imprime un symbole sur chaque bande et déplace ses têtes.
Une machine de Turing multi-bandes peut être formellement décrite comme un 6-tuple (Q, X, B, δ, q 0 , F) où -
Q est un ensemble fini d'états
X est l'alphabet de la bande
B est le symbole vide
δ est une relation sur les états et les symboles où
δ: Q × X k → Q × (X × {Left_shift, Right_shift, No_shift}) k
où il y a k nombre de bandes
q0 est l'état initial
F est l'ensemble des états finaux
Note - Chaque machine de Turing multi-bande a une machine de Turing à bande unique équivalente.