Un prototype programmable pour concrétiser la machine de Turing

Accueil Alan TURING Histoire Machine de Turing Le prototype expérimental réalisé Quelques diagrammes de machines de Turing pour ce prototype Interventions Presse Contact Nouvelle
machine
Machines Idées Descriptif Fonctionnement Technologie 1ère machine de Turing Facile Calculateurs Suites Intéressant Lycées Universités Conférences Vidéos



La premiére des machines-a que Turing donne en exemple : génération des entiers

Nous pouvons construire une machine pour générer la séquence 001011011101111011111...

La machine doit avoir cinq m-configurations, à savoir. "o", "q", "p", "f", "b" et pouvoir écrire les symboles "e", "x", "0", "1".

Les trois premiers symboles sur la bande seront "ee0"; les autres chiffres se succédent sur des carrés alternés. Sur les carrés intermédiaires, on n'imprime rien d'autre que "x". Ces lettres servent à nous "garder la place" et on les efface à la fin. On s'arrange également pour qu'il n'y ait pas de blancs dans la séquence sur les carrés alternés.

Extract of On computable numbers...[Turing 1936]
vol. 2:42, coll. à Proceedings of the London Mathematical Society é,1936 , p. 233

Publication d'Alan TURING 1936


 

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.