La machine de Turing (4)

Utilisation du prototype pour étudier des algorithmes

El 25 abril 2022  - Escrito por  Marc Raynaud Ver los comentarios
Étudier des algorithmes sur un prototype de la machine d’Alan Turing

Le descriptif de sa conception et de sa construction sont sur le site internet : Machinedeturing.com



Dans les articles La machine de Turing (1), La machine de Turing (2) et La machine de Turing (3), nous avons vu les bases de la programmation de ce petit prototype en bois, plexiglas et pièces Lego, ainsi que de nombreux algorithmes qu’il peut exécuter et qui vont nous servir maintenant.

La force du concept imaginé par Alan Turing va être illustrée dans le présent article par le fait de pouvoir exécuter sur cette machine élémentaire des algorithmes particulièrement intéressants en mathématiques.

Vous trouverez, pour certains d’entre-eux, un lien sur une question étudiée dans l’un des articles précédents et quelques rappels historiques.

SOMMAIRE


Exemple 1    Recopier une chaîne de caractères.

Exercice 1    Construire la suite Un = n en binaire.

Exercice 2    Construire la suite des entiers avec le système de codage Gray.

Exemple 2     Bijection entre les entiers naturels et les points du plan de coordonnées entières et positives.

Exercice 3    Générer la suite de Fibonacci.

Exercice 4    Vérifier la conjecture de Collatz (dite aussi conjecture de Syracuse).

Exemple 3 :    Calculer le PGCD de deux entiers écrits en unaire.

Exercice 5    Un castor affairé ( Busy Beaver ) avec 2 états, 2 symboles : 6 cycles.


Et en exercices avec solution différée :

Exercice 6    Passage du codage Gray au système binaire.

Exercice 7    Passage du système binaire au codage Gray.

Exercice 8    Couper une chaîne de caractères en deux parties égales.

Exercice 9    Un castor affairé ( Busy Beaver ) avec 3 états, 2 symboles : 21 cycles.






JPEG - 13.4 KB
JPEG - 3.7 KB

Exemple 1 :     Recopier une chaîne de caractères

Il faudra séparer le traitement du 0 du traitement du 1 et écrire la recopie à droite en sautant une case blanche.

La machine va utiliser deux boucles :

  • États 1, 2, 3, 4 et 5 pour recopier un 0 de la chaîne
  • États 1, 6, 7, 8 et 9 pour recopier un 1 de la chaîne

Le 0 ou le 1 à recopier seront remplacés par un blanc et c’est une gestion précise des déplacements qui permettra d’en retrouver l’emplacement initial et de les remettre à leur valeur initiale.

Suivre sur le diagramme le traitement du 0

L’état 1 remplace le 0 par un blanc, et déplace la tête à droite.
L’état 2 termine le parcours de la chaîne vers la droite, passe un blanc et arrive sur le chiffre de gauche de la recopie.
L’état 3 parcourt la recopie, arrive sur le premier blanc à droite et y écrit le 0.
L’état 4 parcourt la recopie vers la gauche, passe un blanc et se retrouve sur le chiffre de droite de la chaîne.
L’état 5 parcourt la chaîne vers la gauche et quand elle arrive sur un blanc, c’est le blanc sur lequel elle a effacé le 0.

JPEG - 87.5 KB

Pour résumer, il faut quatre états pour traiter le 0 et quatre états pour traiter le 1 ainsi que l’état 1 pour orienter le traitement. On a donc utilisé neuf états pour recopier une chaîne de caractères, cela a été mentionné dans l’article : La machine de Turing (3).

GIF - 1.5 KB

Recopier une séquence





JPEG - 6 KB

Exercice 1
Générer les premiers termes de la suite Un = n en binaire
en commençant avec U1 = 1.

La tête est sur un b au départ.
Pour chaque Un, le recopier à gauche et lui ajouter 1
La recopie de chaque Un se fera en utilisant l’exemple 1.

Solution

JPEG - 103.4 KB

C’est une simple application de la recopie d’une chaîne de caractères.

GIF - 1.5 KB

Suite Un=n en binaire






Pour l’exercice qui suit vous pouvez revoir comment déterminer la parité du nombre de 1 dans une chaîne de caractères dans l’article : La machine de Turing (1).

JPEG - 1.6 KB

Exercice 2 :

Construire la suite des codages des entiers positifs avec le système de codage Gray (dit aussi Gros-Gray)

JPEG - 41.7 KB

On part d’une base constituée d’une suite de 0 dont le nombre dépend du maximum qui sera nécessaire pour un système donné. Par exemple, si le système nécessite huit situations différentes, la base de départ se fera avec trois 0 (23 = 8).

La tête va parcourir cette base de gauche à droite et modifier l’écriture selon la règle :

  • Si il y a un nombre pair de 1, on change le bit de droite;
  • Si il y a un nombre impair de 1, on change le bit à gauche du 1 le plus à droite.

Ensuite, elle revient sur le chiffre de gauche et recommence.

Il faudra arrêter la machine manuellement au bout de 2n -1 cycles.

GIF - 1.5 KB

suite gros gray






Pour l’exemple qui suit vous pouvez revoir comment ajouter 1 ou ôter 1 d’un nombre binaire dans l’article : La machine de Turing (3).

JPEG - 33.2 KB

Exemple 2 :     Établir une bijection entre les entiers naturels et les points du plan de coordonnées entières et positives

JPEG - 83.1 KB

JPEG - 201.1 KB

GIF - 1.5 KB

bijection




JPEG - 1.8 KB

Exercice 3 :

Générer la suite de Fibonacci en unaire

JPEG - 75.4 KB

GIF - 1.5 KB

Fibonacci







Pour l’exercice suivant vous pourrez revoir :

JPEG - 1.9 KB

Exercice 4 :

Vérifier, sur des exemples, la conjecture de Collatz

JPEG - 90.1 KB

GIF - 1.5 KB

Collatz 3





JPEG - 6.2 KB

Exemple 3 :

Calculer le PGCD de deux entiers X et Y écrits en unaire et strictement positifs

Le calcul sera fait en utilisant l’algorithme d’Euclide.

JPEG - 40.3 KB

Solution

JPEG - 112.4 KB


L’état 11 sert à ramener le résultat sur le devant, car avec des nombres un peu grands, le résultat se retrouverait à l’arrière du disque et ne serait pas bien visible.

GIF - 1.5 KB

pgcd





JPEG - 4.1 KB

Exercice 5 :

Castor affairé ou Busy Beaver (2,2)
Vous pouvez consulter l’article de Wikipedia

Il s’agit de trouver l’algorithme qui arrête la machine après avoir fait 6 cycles en utilisant ici 2 états et 2 symboles (b et 1)

GIF - 1.5 KB

castor 2 2






Avec 2 états et 3 symboles, on peut obtenir 38 cycles.
Avec 4 états et 2 symboles, on peut obtenir 107 cycles.
Et, avec l’exercice 9, vous trouverez 21 cycles pour 3 états et 2 symboles.

L’intérêt de l’étude des castors affairés tient au fait que le nombre maximum de cycles qui seront effectués avant l’arrêt, en fonction du nombre de symboles et du nombre d’états, est un bon exemple de nombre non calculable.
De plus, ces nombres ont une croissance qui dépasse l’imagination, par exemple avec simplement 3 états et 3 symboles, ce nombre dépasse 100 000 milliards de cycles.





Quelques recherches, solutions prochainement.

JPEG - 2 KB

Exercice 6 :

Transcrire une écriture en code Gray dans le système binaire

JPEG - 31.4 KB

On utilisera la règle suivante (que nous ne démontrerons pas) :

la tête de lecture parcourt le nombre en partant de la gauche et chaque chiffre est remplacé par :

  • 0 si le chiffre et son précédent calculé sont égaux ;
  • 1 si le chiffre et son précédent calculé sont différents.




JPEG - 2.1 KB

Exercice 7 :

Transcrire un nombre binaire dans le système de codage Gray

JPEG - 31.4 KB

On utilisera la règle suivante (que nous ne démontrerons pas) :

la tête de lecture parcourt le binaire en partant de la gauche et chaque chiffre est remplacé par :

  • 0 si le chiffre et son précédent sont égaux ;
  • 1 si le chiffre et son précédent sont différents.




JPEG - 4.6 KB

Exercice 8 :

Couper une chaîne de caractères en deux parties de même longueur.

On suppose que la chaîne contient un nombre pair de caractères.






JPEG - 4.4 KB

Exercice 9 :

Castor affairé ou Busy Beaver (3,2)

Il s’agit de trouver l’algorithme qui arrête la machine après avoir fait 21 cycles en utilisant ici 3 états et 2 symboles (b et 1).




Post-scriptum :

Tous mes remerciements à Jean-Pierre Escofier qui m’a incité à écrire ces quatre articles et à mes relecteurs, en particulier Ilia Itenberg, Sébastien Kernivinen et Jean-Michel Le Laouénan.
Je remercie aussi toute l’équipe qui participe au contrôle et à la publication des articles, en particulier Carole Gaboriau et Jean Fromentin qui a installé toutes les vidéos sur le site d’Idm.
Merci à tous pour votre accompagnement et vos conseils.

Comparte este artículo

Para citar este artículo:

Marc Raynaud — «La machine de Turing (4)» — Images des Mathématiques, CNRS, 2022

Comentario sobre el artículo

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.