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.