Machines à bande biinfinie

La définition d'une machine à bande biinfinie est identique à celle d'une machine à bande (simplement) infinie excepté le fait que la bande est infinie à droite mais aussi à gauche. Cela signifie de façon plus formelle que la bande est une suite de positions indexées par tous les entiers. Le contenu de la bandes à un instant donné est une suite

… a_-3a_-2a_-1 a₀a₁a₂a₃ …

de symboles de l'alphabet de bande. Au début du calcul, l'entrée initiale est écrite sur les positions 0,...,k de la bande et toutes les autres positions sont remplies par le symbole blanc #. L'entrée est donc délimitée à gauche et à droite par des symboles #. Au début du calcul, la tête de lecture se trouve sur la position 0 de la bande, sur le premier symbole de l'entrée initiale.

Pour montrer que ces machines à bande biinfinie sont aussi puissante que les machine à bande simplement infinie, il faut montrer que toute machine à bande infinie peut être simulée par une machine à bande biinfinie et réciproquement que toute machine à bande biinfinie peut être simulée par une machine à bande infinie. La première simulation est facile. Il suffit de prendre une machine à bande biinfinie qui dès qu'elle trouve un # après un déplacement à gauche revient à droite en laissant inchangée le #. Du coup, elle ne change jamais le contenu des positions d'indices négatifs et elle se comporte comme une machine à bande simplement infinie.

Pour la réciproque, il faut montrer qu'une machine M = (Q,Σ, Γ, E, q₀, F, #) à bande biinfinie peut être simulée par une machine M'= (Q',Σ', Γ', E', q'₀, F', #') à bande infinie. Par simuler, on entend une machine qui accepte exactement les mêmes entrées. L'idée générale est de replier la partie gauche de la bande sous la partie droite pour une obtenir une bande simplement infinie dont les symboles sont des paires de symboles de l'alphabet Γ. Pour simplifier, les positions d'indices -1, -2, -3, ... sont mises sous les positions 1, 2, 3, ... et sous la position 0, on remplit une position par un nouveau symbole $ qu'on suppose ne pas appartenir à Γ. Le contenu ...a_-3a_-2a_-1a₀a₁a₂a₃... de la bande de M sera représenté par le contenu (a₀,$)(a₁,a_-1)(a₂,a_-2)(a₃,a_-3)... de la bande de M'.

Outre l'état de la machine M, la machine M' mémorise si elle est en train de lire la partie supérieure ou la partie inférieure de la bande. Un état de M' sera une paire formée d'un état de Q et d'une élément de {U, D} qui est U (Up) quand elle lit la partie supérieure et D (Down) quand elle lit la partie inférieure de la bande. Les deux première transitions de la machine M' sont chargées de mettre en place le symbole $ dans la partie inférieure de la première position de bande. Pour ces deux transitions, on ajoute deux états q'₀ et q'₁ dont le premier devient l'état initial de la machine M'. Les états finaux de M' sont les paires formées d'un état final de M et d'un élément quelconque de {U, D}. L'alphabet de bande Γ' de la machine M' contient toutes les paires formées de deux symboles de Γ et toutes les paires formées d'un symbole de Γ et du nouveau symbole $. L'entrée initiale est écrite sur la partie supérieure des premières positions de la bandes. L'alphabet d'entrée Σ' de M' contient toutes les paires formées d'un symbole de Σ et du symbole blanc #. Ces données sont résumées ci-dessous.

États : Q'= Q × {U, D} ∪ {q'₀, q'₁}
État initial : q'₀
États finaux : F' = F × {U, D}
Alphabet de bande : Γ' = Γ × (Γ ∪ {$})
Alphabet d'entrée : Σ' = Σ × {#}
Caractère blanc : #' = (#,#)

Les transitions de la machines M' sont les suivantes.

Les premières transitions qui mettent en place le $ dans la partie inférieure de la première position de la bande.
- q'₀,(a,#) → q'₁,(a,$),R est dans E' pour tout a dans Σ.
- q'₁,(a,#) → (q₀,U),(a,#),L est dans E' pour tout a dans Σ. (q₀ est l'état initial de la machine M)
Pour chaque transition p,a → q,b,R de M avec a et b dans Γ, on ajoute à M'
- les transitions (p,U),(a,c) → (q,U),(b,c),R pour tout c dans Γ ∪ {$} (la machine M' lit la partie supérieure de la bande La tête de lecture de M' se déplace dans la même direction que celle de M.)
- les transitions (p,D),(c,a) → (q,D),(c,b),L pour tout c dans Γ (la machine M' lit la partie inférieure de la bande et n'est pas sur la première position la bande. La tête de lecture de M' se déplace dans la direction contraire à celle de M.)
- la transition (p,D),(a,$) → (q,U),(b,$),R (La machine M' lit la partie inférieure de la bande et elle est arrivée sur la première position de la bande. Pour cette transition, elle doit lire sur la partie supérieure de la bande et ensuite elle continue à lire sur la partie supérieure de la bande.)
Pour chaque transition p,a → q,b,L de M avec a et b dans Γ, on ajoute à M'
- les transitions (p,U),(a,c) → (q,U),(b,c),L pour tout c dans Γ (la machine M' lit la partie supérieure de la bande et n'est pas sur la première position la bande. La tête de lecture de M' se déplace dans la même direction que celle de M).
- la transition (p,U),(a,$) → (q,D),(b,$),R (la machine M' lit la partie supérieure de la bande et elle est arrivée sur la première position de la bande. Après cette transition, elle lit sur la partie inférieure de la bande.)
- les transitions (p,D),(c,a) → (q,D),(c,b),R pour tout c dans Γ (la machine M' lit la partie inférieure de la bande et n'est pas sur la première position la bande. La tête de lecture de M' se déplace dans la direction contraire à celle de M).
- la transition (p,D),(a,$) → (q,D),(b,$),R (La machine M' lit la partie inférieure de la bande et elle est arrivée sur la première position de la bande. Pour cette transition, elle doit lire sur la partie supérieure de la bande mais ensuite elle continue à lire sur la partie inférieure de la bande).