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

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 9    Un castor affairé ( Busy Beaver ) avec 3 états, 2 symboles : 21 cycles.

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.

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).

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

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

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).

Exercice 2 :

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

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 (2³ = 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 2ⁿ -1 cycles.

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).

Exemple 2 :     Établir une 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 en unaire

Pour l’exercice suivant vous pourrez revoir :

• Diviser par 2 un nombre pair dans l’article la machine de Turing (3)
  
• Calculer 3n+1 dans l’article la machine de Turing (3)

Exercice 4 :

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

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.

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)

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.

Exercice 6 :

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

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.

Exercice 7 :

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

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.

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.

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).