Réalisation de cette machine avec le prototype
Adaptation au prototype :
-
Le brouillon
La machine de Turing laisse systématiquement un espace entre tous les chiffres qui constituent le résultat attendu. Turing utilise cet espace comme
un "brouillon" et y écrit, selon les besoins, la lettre x. Comme ces espaces sont toujours situés une case sur deux, la lettre particuliére x n'est
pas nécessaire et pour utiliser le prototype, on utilisera le chiffre 1 à la place de cette lettre x.
Les deux lettres ee incluses dans les 2 cases de départ seront simplement remplacées par un 0.
-
Ecriture compactée de la table des transitions
Turing indique que l'on peut regrouper des déplacements sous la forme par exemple de : R,Px,L,L,L.
Pour le prototype, cette transition sera écrite sous la forme de 3 transitions ne contenant chacune qu'un seul déplacement L.
Commentaires sur la table des transitions -->
-
Configuration b :
On a positionné à la main sur le ruban, les lettres qui correspondent à cette configuration, soit : 00_0.
-
Configuration o :
Elle comprenait a l'origine 4 déplacements, elle sera traduite en 4 états (ici de 1 à 4 )
Ecrit les 1 du "brouillon" à droite de chaque 1 d'une séquence et se positionne sur le 0 en début de cette séquence.
Passe à la configuration q
-
Configuration q :
Elle est traduite ici par les états 5 et 6
Déplacement de la téte à droite de 2 en 2 et écriture d'un nouveau 1.
Recul d'une case à gauche et passe à la configuration p.
-
Configuration p :
Elle est traduite ici par les états 7 et 8
Retour de 2 en 2 sur les cases "brouillon"
- Ce retour se termine sur un 1 : Efface ce 1 et passe à la configuration q
- Ce retour se termine sur un 0 : Il s'agit du 0 à gauche du 0 de départ, passe à la configuration f
-
Configuration f :
Elle est traduite ici par les états 9,10 et 11
Déplacement de la téte à droite de 2 en 2 et écriture d'un nouveau 0.
Se déplace d'une case à gauche et passe à la configuration o.
|
