Définitions alternatives

Cours/Algorithmie/Machine de Turing/Définitions alternatives

On a vue que le modèle de la machine de Turing permet de créer des programmes ayant les mêmes structures de contrôle que le pseudo-assembleur. C'est au niveau de la gestion de la mémoire que le modèle de la machine de Turing semble moins complet :

on ne peut lire/écrire qu'au niveau du curseur qui ne peut se déplacer que d'une case par instruction
il n'y a pas de registre

Nous allons montrer que ce n'est qu'une apparence et qu'en réalité, on peut gérer la mémoire exactement comme on le ferait en pseudo-code.

Nous allons pour cela donner 4 définitions alternatives mais équivalentes d'une machine de Turing.

Machine de Turing à accès aléatoire en mémoire

Commençons par un cas simple, le fait de ne pas avoir à se déplacer que de 1 case à la fois :

définition

Une machine de Turing à accès aléatoire en mémoire est composée :

d'un ruban (supposé infini) constitué de cases contiguës pouvant chacune contenir soit le caractère 0 soit le caractère 1
d'un curseur qui est positionné sur une case du ruban (on suppose que le ruban est infini à gauche et à droite du curseur)
d'un ensemble fini $Q$ d'états possibles, contenant les états START et STOP
d'un état courant $q \in Q$
d'une fonction de transition $δ (q, r) = (δ_{e} (q, r), δ_{c} (q, r), δ_{d} (q, r))$ dépendant de l'état $q$ de la machine et du caractère $r$ contenu dans la case du ruban pointée par le curseur. Cette fonction définie sur $Q \times {0, 1}$ permet de modifier :
- l'état de la machine : $δ_{e} : Q \times {0, 1} \mapsto Q$
- le caractère de la case du ruban pointée par le curseur : $δ_{c} : Q \times {0, 1} \mapsto {0, 1}$
- la position du curseur : $δ_{d} : Q \times {0, 1} \mapsto Z$

À l'exécution d'une machine de Turing à accès aléatoire en mémoire, le curseur peut se déplacer d'autant de case vers la droite (si positif) ou la gauche (si négatif) qu'il le souhaite.

Simulation d'une machine à accès aléatoire en mémoire par une machine simple

Comme le nombre de cases où se déplace le curseur est dans la fonction de transition, c'est une constante associée à chaque état. On peut alors pour chaque état ajouter une chaîne d'état se déplaçant que d'une case et modifier la machine à accès aléatoire en mémoire pour qu'elle ne se déplace plus que d'une case à droite ou une case à gauche.

Ainsi, supposons que $δ (q, r) = (δ_{e} (q, r), δ_{c} (q, r), δ_{d} (q, r))$ , on va distinguer 3 cas :

$δ_{d} (q, r) = 0$ : dans ce cas là on modifie la transition et on ajoute 1 états :
1. $δ (q, r) = (q - 0, δ_{c} (q, r), + 1)$
2. $δ (q - 0, s) = (δ_{e} (q, r), s, - 1)$ ( $s$ valant 0 ou 1)
$δ_{d} (q, r) > 1$ : dans ce cas là on modifie la transition et on ajoute $δ_{d} (q, r) - 1$ états :
1. $δ (q, r) = (q - 0, δ_{c} (q, r), + 1)$
2. ...
3. $δ (q - i, s) = (q - (i + 1), s, + 1)$ ( $s$ valant 0 ou 1)
4. ...
5. $δ (q - (δ_{d} (q, r) - 1), s) = (δ_{e} (q, r), s, + 1)$ ( $s$ valant 0 ou 1)
$δ_{d} (q, r) < - 1$ : identique au cas précédent, mais dans l'autre sens.

En appliquant ce procédé à tous les état de la machine, on a maintenant une machine équivalente à la machine précédente mais qui se déplace toujours d'une case vers la droite ou une case vers la gauche : c'est une machine classique.

Equivalence avec la machine de Turing classique

La construction précédente permet d'écrire :

Proposition

Toute machine de Turing à accès aléatoire en mémoire peut être simulée par une machine de Turing simple.

Les deux notions sont donc équivalentes.

Machine à plusieurs curseurs

Une machine de Turing à $k$ curseurs peut être définie comme suit.

définition

Une machine de Turing à $k$ curseurs est composée :

de un ruban (supposé infini) constitué de cases contiguës pouvant chacune contenir soit le caractère 0 soit le caractère 1
de $k$ curseurs, positionnés sur une case de son ruban (on suppose que le ruban est infini à gauche et à droite du curseur)
d'un ensemble fini $Q$ d'états possibles, contenant les états START et STOP
d'un état courant $q \in Q$
d'une fonction de transition $δ (q, c_{1}, \dots, c_{k}) = (δ_{e} (q, c_{1}, \dots, c_{k}), δ_{c_{1}} (q, c_{1}, \dots, c_{k}), \dots, δ_{c_{k}} (q, c_{1}, \dots, c_{k}), δ_{d_{1}} (q, c_{1}, \dots, c_{k}), \dots, δ_{d_{k}} (q, c_{1}, \dots, c_{k}))$ dépendant de l'état $q$ de la machine et des caractères $r_{i}$ contenus dans chaque case des rubans pointée par son curseur associé. Cette fonction définie sur $Q \times {0, 1}^{k}$ permet de modifier :
- l'état de la machine : $δ_{e} : Q \times {0, 1}^{k} \mapsto Q$
- les caractères des cases pointées par chaque curseur $1 \leq i \leq k$ : $δ_{c_{i}} : Q \times {0, 1}^{k} \mapsto {0, 1}$
- les positions des $1 \leq i \leq k$ curseurs : $δ_{d_{i}} : Q \times {0, 1}^{k} \mapsto {\leftarrow, \to}$

Cette machine permet de prendre en compte plusieurs cases du ruban pour les transition. La gestion des curseurs est faite ainsi :

A l'initialisation, les $k$ curseurs sont considérés être sur la même case
A l'exécution, on effectue l'écriture dans l'ordre des curseurs pour rendre déterministe le comportement d'une étape où deux curseurs sont sur la même case.

On va montrer que cette extension n'en est pas vraiment une car on peut toujours transformer une machine à plusieurs curseurs en une machine de Turing normale équivalente.

Nous allons pour cela montrer que l'on peut simuler une machine à 2 curseurs par une machine à un curseur.

Simulation d'une machine à $k$ curseurs par une machine simple

Le principe de cette conversion est d'associer à chaque case du ruban de la machine à deux curseurs, une $(k + 2) - c a s e c o m p o s é d e$ k+2$ cases de la machine à 1 curseur.

Chaque paquet est décomposé ainsi :

case d'indice 0 : une borne. Un marqueur valant 1 pour une case strictement plus à gauche de tous les curseurs (sera utile pour la suite)
case d'indice 1 : un marqueur valant 1 si le curseur 1 est est dans la case, 0 sinon
case d'indice 2 : un marqueur valant 1 si le curseur 2 est est dans la case, 0 sinon
...
case d'indice $k$ : un marqueur valant 1 si le curseur $k$ est est dans la case, 0 sinon
case d'indice $k + 1$ : valeur de la case associée

Par exemple si l'on a la machine à 2 curseurs suivante :

numéro case :  12345
ruban       :  00101
curseurs    :   ^ ^
                1 2

Machine à 1 curseur simulant la machine :

case machine à 2 curseurs : 1   2   3   4   5
ruban                     : 10000100000100100001
indice paquet de 4 cases  : 01230123012301230123

On initialise la machine comme suit :

ruban                     : 10000110000000000000
curseur                   : ^
indice paquet de 4 cases  : 01230123012301230123

L'idée force est de multiplier les états de la machine pour stocker l'état de tous les curseur et le nouvel état vers lequel aller. Ceci est possible car il n'y a que 2 possibilités de valeur pour chaque case (0 ou 1) et un nombre fini d'états. Pour chaque état $q$ , on va ajouter $3^{k} \cdot (| Q | + 1)$ états : $(q, c_{1}, \dots, c_{k}, q^{'})$ où chaque $c_{k} \in x, 0, 1$ et $q^{'} \in Q \cup z$ (on suppose sans perte de généralité que $z \notin Q$ ). On rajoute donc beaucoup d'états mais toujours un nombre fini.

On suppose que l'on est dans le cas où la machine à 1 ruban simulant la machine à deux rubans est telle que :

son état est $q$
une seule case contient le marqueur du curseur $i$ à 1 ( $1 \leq i \leq k$ )
une seule case contient le marqueur de la borne à 1 et est strictement à gauche des marqueurs des curseurs 1 et 2
le curseur est placé sur la case contenant le marqueur de borne

Les différentes étapes ci-après permettent de simuler l'avancement de la machine à $k$ rubans d'un état. Là où une machine $k$ rubans traite l'état $q$ en une étape, nous ferons les 5 étapes suivantes :

préparer le nouvel état :
1. passer de l'état $q$ à l'état $(q, x, \dots, x, z)$
trouver l'état actuel. On exécute la procédure suivante avec les paramètres $(i, q, x, \dots, x, z)$ pour $i$ allant de 1 à k:
1. se déplacer de $i$ cases vers la droite
2. si 1 sur le ruban aller en 5
3. se déplacer de $k + 2$ cases vers la droite
4. aller en 1
5. se déplacer de $k - i$ cases vers la droite
6. passer de l'état $(i, q, c_{1}, \dots, c_{k}, z)$ à l'état $(i, q, c_{1}^{'}, \dots, c_{k}^{'}, z)$ où :
  - $c_{j}^{'} = c_{j}$ pour tout $j \neq i$
  - $c_{i}^{'}$ vaut la valeur du ruban (1 ou 0)
7. se déplacer de $k + 1$ cases vers la gauche
8. se déplacer de $k + 2$ cases vers la gauche
9. si 0 sur le ruban aller en 7.
passer de l'état $(q, c_{1}, \dots, c_{k}, z)$ à l'état $(q, c_{1}, \dots, c_{k}, δ_{e} (q, c_{1}, \dots, c_{k}))$
Écriture des nouvelles valeurs sur le ruban. On exécute la procédure suivante avec les paramètres $(i, q, c_{1}, \dots, c_{k}, q^{'})$ pour $i$ allant de 1 à k:
1. se déplacer de $i$ cases vers la droite
2. si 1 sur le ruban aller en 5
3. se déplacer de $k + 2$ cases vers la droite
4. aller en 1
5. se déplacer de $k - i$ cases vers la droite
6. placer $δ_{c_{i}} (q, c_{1}, \dots, c_{k})$ sur le ruban
7. se déplacer de $k + 1$ cases vers la gauche
8. se déplacer de $k + 2$ cases vers la gauche
9. si 0 sur le ruban aller en 7.
Déplacement des curseurs. On exécute la procédure suivante avec les paramètres $(i, q, c_{1}, \dots, c_{k}, q^{'})$ pour $i$ allant de 1 à k:
1. se déplacer de $i$ cases vers la droite
2. si 1 sur le ruban aller en 5
3. se déplacer de $k + 2$ cases vers la droite
4. aller en 1
5. écrire 0 sur le ruban
6. si $δ_{d_{i}} (q, c_{1}, \dots, c_{k}) =\to$ se déplacer de $k + 2$ cases vers la droite, sinon $k + 2$ cases vers la gauche
7. écrire 1 sur le ruban
8. se déplacer de $i$ cases vers la gauche
9. si 0 sur le ruban aller en 14.
10. écrire 0 sur le ruban
11. se déplacer de $k + 2$ cases vers la gauche
12. écrire 1 sur le ruban
13. aller en 15
14. se déplacer de $k + 2$ cases vers la gauche
15. si 0 sur le ruban aller en 14.
fin de transition :
1. passer de l'état $(q, c_{1}, \dots, c_{k}, δ_{e} (q, c_{1}, \dots, c_{k}))$ à l'état $δ_{e} (q, c_{1}, \dots, c_{k})$

Après ces 6 méta-étapes, la machine est de nouveau dans un état stable et peut recommencer son cycle.

Les étapes précédentes peuvent être écrite en utilisant le formalisme des compositions de machine. Ceci fonctionne car $k$ est une constante et le nombre d'états fini. On peut donc utiliser les procédures qui génèrent autant d'états que nécessaire.

Exemple

Supposons que l'on ait la machine à deux ruban suivante :

numéro case :  12345
ruban       :  010101
curseurs    :    ^ ^
                 2 1

Et qu'il soit simulé par la machine à 1 ruban :

indice paquet de 4 cases  : 012301230123012301230123
ruban                     : 000010010010000101000001
curseur                   :     ^

On veut passer de à l'état $δ (q, 0, 0) = (q^{'}, 1, 0, \to, \leftarrow)$ . On montre chaque fin d'étape

indice 4-cases          : 012301230123012301230123
étape - état
1     - (q, x, x, z)    : 000010010010000101000001
                        :     ^
2.1   - (1, q, x, x, z) : 000010010010000101000001
                        :      ^
...

TBD finir l'exemples faire l'exemple avec 2 curseurs. Parler des différentes parties. En particulier le décalage de la borne

Cela fait tout un tas de transitions, mais on arrive bien à simuler les $2$ curseurs par un seul !

Equivalence avec la machine de Turing classique

Proposition

Toute machine de Turing à $k$ curseurs peut être simulée par une machine de Turing simple.

Les deux notions sont donc équivalentes.

Machine à plusieurs rubans

Une machine de Turing à $k$ rubans peut être définie comme suit.

définition

Une machine de Turing à $k$ rubans est composée :

de $k$ rubans (supposés infinis) constitués de cases contiguës pouvant chacune contenir soit le caractère 0 soit le caractère 1
de $k$ curseurs, un par ruban, positionnés sur une case de son ruban (on suppose que le ruban est infini à gauche et à droite du curseur)
d'un ensemble fini $Q$ d'états possibles, contenant les états START et STOP
d'un état courant $q \in Q$
d'une fonction de transition $δ (q, r_{1}, \dots, r_{k}) = (δ_{e} (q, r_{1}, \dots, r_{k}), δ_{c_{1}} (q, r_{1}, \dots, r_{k}), \dots, δ_{c_{k}} (q, r_{1}, \dots, r_{k}), δ_{d_{1}} (q, r_{1}, \dots, r_{k}), \dots, δ_{d_{k}} (q, r_{1}, \dots, r_{k}))$ dépendant de l'état $q$ de la machine et des caractères $r_{i}$ contenus dans chaque case des rubans pointée par son curseur associé. Cette fonction définie sur $Q \times {0, 1}^{k}$ permet de modifier :
- l'état de la machine : $δ_{e} : Q \times {0, 1}^{k} \mapsto Q$
- les caractères des cases de chaque ruban $1 \leq i \leq k$ pointées par les curseurs : $δ_{c_{i}} : Q \times {0, 1}^{k} \mapsto {0, 1}$
- les positions des $1 \leq i \leq k$ curseurs : $δ_{d_{i}} : Q \times {0, 1}^{k} \mapsto {\leftarrow, \to}$

L'exécution est alors identique à la machine simple. Tout se passe comme si on avait $k$ machines différentes, mais un seul état et une fonction de transition dépendant de tous les rubans.

De même, l'entrée et la sortie se généralise aisément en considérant l'ensemble des $k$ rubans.

Cette généralisation semble permettre plein de choses nouvelles ! Mais il n'en est rien : on peut toujours transformer une machine à plusieurs rubans en une machine de Turing normale équivalente.

Pour prouver ceci, nous allons montrer que l'on peut simuler une machine à 2 rubans par une machine à 1 ruban. Ceci va prendre plusieurs étapes.

Simulation d'une machine à 2 rubans par une machine classique

Représentons une machine à 2 rubans par le schéma suivant :

curseur 1 :              v
ruban 1   : ...000111001001001...
ruban 2   : ...000111001001001...
curseur 2 :       ^

A priori les deux rubans sont décorrélées, mais comme à l'initialisation les deux rubans sont remplis de 0, les deux rubans peuvent être considérés comme superposés :

curseur 1 :           v
ruban 1   : ...000000000000000...
ruban 2   : ...000000000000000...
curseur 2 :           ^

déplace de deux
superpose les 2 rubans en affectant les cases paire au ruban 1 et les cases impaires au ruban 2

Une machine à deux rubans est donc équivalente à une machine à un ruban et 2 curseurs. Chaque curseur :

curseur 1     :           v
ruban         : ...000000000000000...
curseur 2     :            ^
ruban initial :    212121212121212

On modifie également la fonction de transition pour qu'elle se déplace de 2 cases à chaque déplacement de curseur.

Equivalence avec la machine de Turing classique

La procédure précédente peut se généraliser à $k$ rubans et on peut alors simuler une machine à $k$ rubans par une machine à $k$ curseur elle-même simulation par une machine classique :

Proposition

Toute machine de Turing à $k$ rubans peut être simulée par une machine de Turing simple.

Les deux notions sont donc équivalentes.

Machines à plusieurs curseurs et rubans

On peut bien sur combiner les deux approches et construire une machine de Turing à $k$ rubans et $k^{'}$ curseurs répartis sur les rubans. Mais, comme vous devez vous en douter :

Proposition

Toute machine de Turing à $k$ rubans et $k^{'}$ curseurs peut être simulée par une machine de Turing simple.

Les deux notions sont donc équivalentes.

preuve

En utilisant les technique de preuve précédentes on arrive facilement à montrer que :

toute machine de Turing à $k$ rubans et $k^{'}$ curseurs peut être simulée par une machine de Turing $1$ rubans et $k^{'}$ curseurs.
toute machine de Turing à $k$ rubans et $k^{'}$ curseurs peut être simulée par une machine de Turing $k$ rubans et $1$ curseur.

Alphabets

Ne travailler qu'avec des 0 et des 1 peut sembler réducteur :

définition

Une machine de Turing sur un alphabet $A$ est composée :

d'un ensemble fini $A$ nommé alphabet
un caractère blanc, élément de $A$
d'un ruban (supposé infini) constitué de cases contiguës pouvant chacune contenir des caractères de $A$
d'un curseur qui est positionné sur une case du ruban (on suppose que le ruban est infini à gauche et à droite du curseur)
d'un ensemble fini $Q$ d'états possibles, contenant les états START et STOP
d'un état courant $q \in Q$
d'une fonction de transition $δ (q, r) = (δ_{e} (q, r), δ_{c} (q, r), δ_{d} (q, r))$ dépendant de l'état $q$ de la machine et du caractère $r$ contenu dans la case du ruban pointée par le curseur. Cette fonction définie sur $Q \times A$ permet de modifier :
- l'état de la machine : $δ_{e} : Q \times A \mapsto Q$
- le caractère de la case du ruban pointée par le curseur : $δ_{c} : Q \times A \mapsto A$
- la position du curseur : $δ_{d} : Q \times A \mapsto {\leftarrow, \to}$

L'exécution est alors identique à la machine simple, sauf pour l'initialisation où le ruban est rempli de caractères blanc plutôt que de 0.

Equivalence avec la machine de Turing classique

On simule une machine de Turing sur un alphabet $A$ par une machine de Turing à $| A | - 1$ rubans.

L'idée est d'associer chaque caractère de $A$ par un $(A - 1)$ -uplet valant :

$(0, \dots, 0)$ pour le caractère blanc
$(0, \dots, 0, 1, 0, \dots, 0)$ pour un caractère donné

Par exemple si $| A | = a, b, c$ avec b valant blanc, on a :

$(0, 0)$ associé à $b$
$(1, 0)$ associé à $a$
$(0, 1)$ associé à $c$

La fonction de transition de la machine est alors répartie sur les rubans. Par exemple si $δ (q, a)$ fait aller la machine originale à droite, écrit $c$ la machine et change l'état en $q^{'}$ , la machine à 2 rubans va avoir comme transition :

$δ_{1} (q, 1, 0) = (q^{'}, 0, \to)$
$δ_{2} (q, 1, 0) = (q^{'}, 1, \to)$

De façon formelle. Soit une machine de Turing sur un alphabet $A$ de fonction de transition $δ$ et une bijection $ϕ : A \mapsto {0, d o t s, A - 1}$ qui associe 0 au caractère blanc.

On construit la fonction de transition de la machine à $A - 1$ ruban telle que si $δ (q, a) = (q^{'}, a^{'}, f)$ alors pour le $A - 1$ -uplet $(0, \dots, 0, 1, 0, \dots, 0)$ tel que le 1 est à la position $ϕ (a)$ , on a :

$δ_{i} (q, 0, \dots, 0, 1, 0, \dots, 0) = (q^{'}, 0, f)$ si $i \neq ϕ (a^{'})$
$δ_{i} (q, 0, \dots, 0, 1, 0, \dots, 0) = (q^{'}, 1, f)$ si $i = ϕ (a^{'})$

On a donc simulé une machine de Turing d'alphabet $A$ par une machine de TUring à $k$ rubans et comme une machine de Turing à $k$ rubans peut être simulée par une machine de Turing, on en conclut :

Proposition

Toute machine de Turing d'alphabet $A$ peut être simulée par une machine de Turing simple.

Les deux notions sont donc équivalentes.

Machine de Turing `01#`

La définition d'une machine de Turing la plus couramment utilisée en algorithmie théorique est la machine de Turing d'alphabet ${0, 1, ♯}$ avec # comme caractère blanc et la possibilité de ne pas avancer le ruban :

définition

Nous nommerons : Machine de Turing 01# une machine $M$ de Turing d'alphabet ${0, 1, ♯}$ avec # comme caractère blanc avec les caractéristiques suivantes :

$δ_{d} (q, r)$ (ou les $δ_{d_{i}} (q, r_{1}, \dots, r_{p})$ si la machine possède plusieurs rubans ou curseurs) prend ses valeurs dans ${\leftarrow, \emptyset, \to}$ . Si la valeur est $\emptyset$ le curseur ne bouge pas.
la sortie Machine de Turing 01# sera la portion de ruban entourant le curseur du premier caractère blanc à la gauche de celui-ci exclu au premier caractère blanc à la droite de celui-ci exclu.
l'entrée sera :
- $M (E)$ avec $E$ uniquement composée de 0 ou de 1
- $M ([E])$ avec $[E] = E_{1} ♯ . . . ♯ E_{i} ♯ . . . ♯ E_{n}$ avec les E_i uniquement composée de 0 ou de 1

Une machine Machine de Turing 01# à $k$ rubans aura comme entrée $M (E_{1}, \dots, E_{k})$ , $M ([E_{1}], \dots, [E_{k}])$ ou une combinaison de ceux-ci.

La fait d'accepter de ne pas se déplacer permet des transitions de type $δ_{i} (q, r_{1}, \dots, r_{p}) = (q, r_{i}, \emptyset)$ pour tout $i \neq I$ et $δ_{I} (q, r_{1}, \dots, r_{p}) = (q, r_{I}^{'}, \leftarrow)$ . On peut bouger les rubans indépendamment les uns des autres !

Mais, comme toujours, ce n'est qu'une facilité d'écriture, on ne peut faire plus qu'avec une machine de Tuning simple :

Proposition

On peut simuler une machine de Turing 01# à plusieurs rubans et plusieurs curseurs par une machine de Turing.

preuve

Il nous faut juste montrer que l'ajout de transitions où le curseur d'un ruban ne bouge pas peut être simulé par une machine de Turing.

Pour cela on ne va écrire que sur les cases paires du ruban et ajouter des état tampons permettant de simuler le sur place. Ci après un exemple avec 2 rubans et on suppose que le second ruban ne bouge pas alors que le premier va à droite (les autres cas sont identiques):

curseur du ruban 1 :     v
parité de la case  : 01010101010
curseur du ruban 2 :     ^

Premier état tampon, on se déplace sur une case impaire. Celui qui doit bouger avance et celui qui doit rester sur place recule :

curseur du ruban 1 :      v
parité de la case  : 01010101010
curseur du ruban 2 :    ^

Second état tampon, les deux se déplacent dans la même direction :

curseur du ruban 1 :       v
parité de la case  : 01010101010
curseur du ruban 2 :     ^

Définitions alternatives

Machine de Turing à accès aléatoire en mémoire

Simulation d'une machine à accès aléatoire en mémoire par une machine simple

Equivalence avec la machine de Turing classique

Machine à plusieurs curseurs

Simulation d'une machine à k curseurs par une machine simple

Exemple

Equivalence avec la machine de Turing classique

Machine à plusieurs rubans

Simulation d'une machine à 2 rubans par une machine classique

Equivalence avec la machine de Turing classique

Machines à plusieurs curseurs et rubans

Alphabets

Equivalence avec la machine de Turing classique

Machine de Turing 01#

Simulation d'une machine à $k$ curseurs par une machine simple

Machine de Turing `01#`