Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Apprenez à programmer avec une machine de Turing ! Marc Raynaud(*) Descriptifs

Apprenez à programmer avec une machine de Turing ! Marc Raynaud(*) Descriptifs techniques, diagrammes et vidéos sur le site : www.machinedeturing.org Nous présentons dans cet article un prototype de la machine imaginée par Alan Turing pour modéliser le concept d’algorithme et donner une réponse négative au problème de la décision en logique du premier ordre posé quelques années auparavant par Hilbert et Ackermann. Pour simplifier, est-il possible de trouver une méthode « effectivement calculable » pour décider si une proposition est démontrable ou non ? Si ce problème mathématique est difficile, le fonctionnement de sa machine est abordable par un large public et vous trouverez ci-dessous de nombreux exemples à proposer à vos élèves. Alan Turing (1912-1954) est un mathématicien britannique. Il obtient sa licence en 1934 au King’s Collège de Cambridge. Il passe ensuite sa thèse à Princeton aux États-Unis. Le prototype présenté ici est directement issu de la description qu’il a donnée dans son article publié en 1936 et intitulé : On Computable Numbers, with an Application to the Entscheidungsproblem (problème de la décision). Vous trouverez le texte initial sur le site : www.machinedeturing.org onglet machine de Turing. Alan Turing n’a jamais construit cette machine. J’ai simplement ajouté un lecteur de feuilles perforées qui permet de le programmer facilement. L’intérêt de ce prototype est qu’il permet de mettre en œuvre un très Programmer avec une machine de Turing 471 APMEP no 510 (*) professeur de mathématiques à la retraite. grand nombre d’algorithmes dont on peut immédiatement visualiser le fonctionnement. C’est aussi une belle illustration du génie de ce grand mathématicien. 1. Description théorique de la machine Un ruban infini comporte des cases qui peuvent contenir des symboles ; une tête d’écriture et de lecture peut se déplacer sur ce ruban. La tête peut lire le symbole déjà écrit, en écrire un autre et se déplacer d’une case à gauche ou d’une case à droite. Les actions à exécuter (écriture, déplacement et choix d’un état) sont inscrites dans ce qu’on appelle les états. L’ensemble des états possibles est regroupé dans la table des transitions. 2. Exemple détaillé Trouver une séquence et en remplacer les 0 par des 1 Une séquence de 0 et de 1 est écrite sur le ruban et la tête est à gauche de cette séquence. Pour cet algorithme, on utilise deux états : À l’état 1 Æ la tête devra se déplacer à droite tant qu’elle lira un blanc, dès qu’elle trouve un 0 ou un 1 elle passe à l’état 2. À l’état 2 Æ si elle lit un 0, elle écrit 1 et se déplace à droite ; Æ si elle lit un 1, elle n’écrit rien et se déplace à droite ; Æ enfin, si elle lit un blanc, c’est qu’elle a fini de parcourir la séquence, elle passe à l’état final et s’arrête. On construit le diagramme de la machine de la façon suivante : Les états sont écrits sous la forme q1, q2, etc. et qF représente l’état final. 472 Pour chercher et approfondir APMEP no 510 Les déplacements à gauche et à droite sont représentés par les lettres L et R (Left et Right) Les triplets indiqués représentent (lecture ; écriture ; déplacement) et la flèche indique le prochain état. Dans l’état 1 (q1) : Le triplet (b ; ; R) avec la flèche signifie que si la tête lit un blanc, elle n’écrit rien, elle se déplace d’une case à droite et elle reste à l’état 1. Les triplets (0 ; ; ) et (1 ; ; ) signifient que si la tête lit un 0 ou un 1, elle n’écrit rien, elle ne se déplace pas et elle passe à l’état 2. Dans l’état 2 (q2) : Le triplet (0 ; 1 ; R) signifie que si la tête lit un 0, elle écrit 1, elle se déplace à droite et elle reste à l’état 2. Le triplet (1 ; ; R) signifie que si la tête lit un 1, elle n’écrit rien, elle se déplace à droite et elle reste à l’état 2. Le triplet (b ; ; ) signifie que si la tête lit un blanc, elle n’écrit rien, elle ne se déplace pas et elle passe à l’état final qF. Le diagramme complet est le suivant : Et voila le résultat Représentation de la machine en fonctionnement. Le trapèze représente la tête de lecture/écriture. On voit clairement ici que la tête de lecture ne fait que se déplacer de la gauche vers la droite (ce n’est pas le cas général) et que dans l’état 2 elle remplace les 0 par des 1. Programmer avec une machine de Turing 473 APMEP no 510 L’état final qF provoque l’arrêt de la machine. Exercices associés : – Ajouter un 1 à droite d’une séquence, la tête étant sous le chiffre de gauche. – Remplacer, dans une séquence, tous les 1 par des 0 et tous les 0 par des 1. – Écrire la suite infinie : 10101010… (il n’y a rien sur le ruban au départ). Solutions plus loin dans l’article. 3. Description du prototype Le ruban Il comporte 100 petits cylindres avec 3 positions, alphabet {b,0,1} : • b (blanc) : le cylindre est enfoncé totalement • 0 : le cylindre est à mi-hauteur (7mm) • 1 : le cylindre est relevé à pleine hauteur (14mm) À noter : Le ruban est ici « replié sur lui-même » sous la forme d’un disque… si le nombre de cylindre est fini (100), le ruban est quand à lui illimité ! Les états Le commutateur des états comprend 12 états, de l’état initial 1 à l’état final 12 qui provoque l’arrêt de la machine. Ce mécanisme retourne, pour chaque état, le résultat de la lecture à la table des transitions. Dans la machine théorique, le nombre d’états est fini. Mécanisme de lecture Un petit moteur pousse une tige contre les cylindres, la position d’arrêt indique la hauteur des cylindres. Les relais permettent de garder en mémoire le résultat d’une lecture jusqu’à la suivante. 474 Pour chercher et approfondir APMEP no 510 Voir sur le site www.machinedeturing.org onglet descriptif comment un relais peut servir de mémoire. Mécanisme d’écriture Deux petits moteurs «LEGO» poussent des tiges qui agissent sur les cylindres pour les faire monter ou descendre. Pour écrire un blanc, le moteur du haut pousse complètement un cylindre vers le bas. Pour écrire un 0 (cylindre à mi-hauteur), les deux moteurs agissent en même temps. Pour écrire un 1, le moteur du bas pousse complètement un cylindre vers le haut. Table des transitions Elle permet de définir, pour chaque état, selon le résultat de la lecture, les actions à exécuter : Æ Écriture Æ Déplacement Æ Choix d’un nouvel état Ces actions sont facultatives. La feuille est percée de trous et placée dans le lecteur. 612 pointes appuieront sur la feuille et là où il y a des trous, des contacts électriques seront établis avec des bandes de cuivre qui transmettront les actions à faire au dispositif. Ces feuilles percées de trous (tables des transitions) constituent les programmes de la machine. À noter : ce prototype a été réalisé avec des technologies existant à l’époque de Turing Programmer avec une machine de Turing 475 APMEP no 510 4. Quelques diagrammes pour débuter a) Faire une addition en unaire Écrire un nombre en unaire revient à écrire autant de 1 que la valeur du nombre, exemple 5 s’écrit 11111. Il faut additionner deux nombres représentés par des 1 (dans cet exemple 2 et 3), et séparés par un espace blanc. Pour cela la tête de lecture va parcourir le premier nombre, arrivée sur le blanc, elle va écrire un 1, puis elle va parcourir le deuxième nombre, arrivée au blanc elle va reculer d’une case et va terminer en mettant à blanc le 1 le plus à droite. État 1 : la tête se déplace vers la droite jusqu’à trouver un blanc Quand elle trouve un blanc, elle écrit 1, puis se déplace à droite et passe à l’état 2 État 2 : la tête se déplace de nouveau vers la droite jusqu’à trouver un blanc Quand elle a trouvé un blanc, elle recule d’une case pour se mettre sur le 1 le plus à droite. 476 Pour chercher et approfondir APMEP no 510 État 3 : Elle écrit un blanc à la place du dernier 1 et passe à l’état final pour s’arrêter. La table des transitions est la suivante : Et le diagramme correspondant Exercice associé : Faire une soustraction en unaire : deux nombres X et Y sont écrits en unaire et séparés par un blanc, X est inférieur à Y et la tête est sous le chiffre de gauche de X. On pourra, successivement, remplacer un 1 de X par un 0 et supprimer un 1 de Y. Solution plus loin dans l’article. b- Nombre pair de 1 Une séquence de 0 et de 1 est écrite sur le ruban, la question posée à la machine uploads/Litterature/ aaa14058.pdf