La théorie : la machine de TURING.
La machine de Turing est une bande magnétique avec des codes lus par une tête de lecture.
Le principe est simple : il s'agit d'une machine de transition. La tête de lecture constate l'état dans lequel on se trouve et identifie le code inscrit sur la case. En fonction de celui-ci, elle inscrit le code qui lui est indiqué par l'état du moment,puis passe à l'état suivant en se déplacant également d'une case vers la gauche ou vers la droite. Le systême de codage est assez simple. En règle générale, on utilise 0, 1, # ou * ou parfois 2 et pour le déplacement -1 ou +1. Le tout permet d'obtenir des lignes de programmation de ce style:
(état, code lu) = (nouvel état, code écrit, direction)
La machine de Turing est totalement déterministe. L'état est prédéterminé, il n'y a pas de libre arbitre. Une fois qu'on a le programme, on sait toujours comment les choses vont se passer. Les mêmes causes produisent toujours les mêmes effets. N'étant pas séquentielles, les lignes peuvent être écrites dans n'importe quel ordre. Cependant aucune ne doit avoir le même test de départ qu'une autre ligne.
Mais sans doute comprendrez vous mieux grâce à un ou deux exemples. Pour une meilleure compréhension, se sont des exmples "fait main" puis scannés. Si mon écriture ne vous convient pas...écrivez moi !!
Exemple 1° : une machine simple.
On suppose la bande vide à gauche de l'étoile (*) de gauche et à droite des 0. On veut remplacer les 1 par des 0 et les 0 par des 1. La flêche sous l'étoile de gauche indique l'état de départ (E0).
on a alors :
(E0, *) = (E1, *, D). on change d'état pour commencer le déplacement.
(E1, 1) = (E1, 0, D). on remplace les 1 par des 0 et cela jusqu'à tomber sur l'étoile de droite.
(E1, *) = (E2, *, D). on change d'état pour le bon fonctionnement du cycle.
(E2, 0) = (E2, 1, D). on remplace les 0 par des 1 et cela jusq'à tomber sur le vide aprés le dernier 0.
(E2, vide) = FIN. on a ici la condition d'arrêt.
Toutes les machine de Turing fonctionnent sur le même principes. Aller...
Exemple 2° : plus compliqué.
On suppose la bande vide à gauche de l'étoile de gauche et à droite de celle de droite. Entre les deux étoiles, des 1. On veut, en partant de l'état de départ (flêche), placer autant de 0 à droite de l'étoile de droite que de 1 entre les deux étoiles. Par la même occasion on remplacera les 1 par des 0.
On a alors :
(E0, *) = (E1, *,D). on change d'état pour commencer le déplacement.
(E1, 1) = (E2, 0, D). on change d'état car il est possible de trouver un 1 encore aprés et cela peut géner le programme.
(E2, 1) = (E2, 1,D). on ne change pas d'état et on continu vers la droite.
(E2, *) = (E3, *, D). on change d'état pour le bon fonctionnement du cycle.
(E3, vide) = (E3, 0, G). on place un 0 à la place du vide et on part vers la gauche.
(E3, 0) = (E3, 0, D). on ne change pas d'état car se sont les vides que l'on cherche. Cette ligne n'intervient qu'aprés au moins une passe de programme.
(E3, *) = (E4, *, G). on change d'état pour le bon fonctionnement du cycle. De plus E4 nous permet de revenir à la première étoile.
(E4, 1) = (E4, 1, G). on se dirige vers la première étoile.
(E4, 0) = (E4, 0, G). on se dirige vers la première étoile.
(E4, *) = (E1, *, D). on recommence le cycle.
(E1, 0) = (E1, 0, D). on ne change pas d'état car on cherche les 1.
(E1, *) = FIN. c'est la condition d'arrêt. Tous les 1 sont maintenant des 0 et il y a autant de 0 à droite de l'étoile de droite que de 0 entre les deux étoiles.
Si vous voulez m'envoyer certaines de vos machines pour que je les corrige je suis tout à fait d'accord. Merci aux courageux !!
Précédent : Représentation pratique.
Suite : Des principes.
Retour à la page principale.