Machines à plusieurs bandes

Les machines à plusieurs bandes sont une extension des machines de Turing introduites au début. Elles ont un contrôle fini constitué d'un nombre fini d'états. Au lieu de disposer d'une seule bande infinie, elles diposent de plusieurs bandes sur lesquelles elle lisent et écrivent. Pour ce faire, la machine dipose d'une tête de lecture/écriture sur chacune de ses bandes. Ces têtes de lecture/écriture se déplacent indépendamment sur chacune des bandes.

Voici la définition d'une machine de Turing à k bandes où k est un entier strictement positif. Une machine de Turing M est un septuplet (Q,Σ, Γ, E, q₀, F, #) où

Q

est l'ensemble des états

Σ

est l'alphabet d'entrée.

Γ

est l'alphabet de bande.

E

est l'ensemble des transitions.

q₀

est l'état initial.

F

est l'ensemble des états finaux appelés aussi états d'acceptation

#

est le symbole blanc.

Il est important de noter que les transitions de la machines dépendent de l'état interne mais aussi des k symboles que la machine lit sur les k bandes. Chaque transition détermine les k symboles qui sont écrits sur les k bandes et les déplacements de chacune des têtes sur les k bandes. Chaque transition a donc la forme p, a₁,…,a_k → q,b₁,…,b_k, x₁,…,x_k, où les x₁,…,x_k sont des éléments de {L, R, S}. L'état p est l'état de contrôle de la machine avant la transition et q est le nouvel état de contrôle après la transition. Les symboles a₁,…,a_k sont les symboles lus sur chacune des k bandes et les symboles b₁,…,b_k sont les symboles écrits sur chacune des k bandes. Les éléments x₁,…,x_k indiquent les mouvements des k têtes de lecture. Un L (Left) signifie un déplacement d'une position vers la gauche, un R (Right) signifie un déplacement d'une position vers la droite et un S (Stay) signifie que la tête reste sur la position où elle est avant la transition.