Dans l’article « La machine de Turing (1) », nous avons vu la description générale du système et comment les lignes des tables des transitions représentent les étapes de l’exécution d’un algorithme. Nous avons appliqué cela aux positionnements de la tête de lecture/écriture et aux traitements de base des chaînes de caractères.

Si nous voulons nous placer sur un plan plus général et théorique, nous dirons que notre machine de Turing est constituée de :

Ces six points constituent la base à retenir pour la suite de ces articles.

Pour commencer, nous allons voir une méthode pour représenter graphiquement les tables des transitions sous la forme de diagrammes. Les schémas visuels permettent souvent de mieux comprendre l’enchaînement des étapes dans le déroulement d’un processus.
Après de nombreux exemples et quelques exercices simples, vous serez familiarisés avec ces représentations graphiques et vous pourrez plus facilement aborder des algorithmes pour effectuer des calculs et des opérations. Dans cet article, nous travaillerons uniquement avec des nombres écrits en unaire, les calculs en binaire se feront dans l’article suivant.

A) Les diagrammes de Turing

Les informations écrites à côté de la flèche sont dans l’ordre : Lecture, Écriture, Déplacement.

Exercice 1

Par la suite, nous ne mentionnerons plus les lignes vides.

Exercice 2

Exercice 3

Vous observez une équivalence entre les tables de transitions et les diagrammes, cela vous laissera le choix de l’outil pour rechercher la solution d’un exercice.

Exercice 4

Exercice 5

Exercice 6

B) Opérations et calculs avec des nombres écrits en unaire

Un nombre entier positif n écrit en unaire est simplement une suite de n chiffres 1 .

Donnons quelques exemples.

• Le nombre 1 en unaire s’écrit 1.
• Le nombre 3 en unaire s’écrit 111.
• Le nombre 7 en unaire s’écrit 1111111.
• Le zéro correspond à l’absence de 1, il apparaîtra sous la forme d’une case blanche.
  
  

Nous pouvons appliquer à des suites de 1 ce que nous avons vu dans l’article « La machine de Turing (1) » pour le traitement des chaînes de caractères. Cela est particulièrement adapté pour l’addition de deux entiers écrits en unaire.

Tous les nombres traités dans cette partie sont des entiers naturels

Addition de deux unaires

      Deux nombres X et Y sont écrits en unaire et séparés par un blanc.
      La tête est sous le 1 de gauche du premier nombre.
      Établir un algorithme qui calcule la somme X+Y.

Première méthode

Deuxième méthode

          Concaténer les deux suites de 1, cela a été vu dans l’article précédent, exercice 15.

Troisième méthode

        
Copier les 1 de X à droite de Y, c’est-à-dire obtenir la concaténation de Y et X dans cet
        ordre.

Pour ne pas perdre la valeur d’un unaire pendant son traitement, on remplace chaque 1 par un 0.
A la fin du calcul, en remplaçant chaque 0 par un 1, on retrouve le nombre initial.

Exercice 7

Deux nombres X et Y sont écrits en unaire sur le ruban et séparés par un blanc.
La tête est sous le 1 de droite de Y.
Établir un algorithme qui calcule la somme X+Y et qui écrit cette somme à droite de Y. Il doit se terminer en remettant X et Y à leur valeur initiale.

La recherche du minimum d’états à utiliser pour résoudre un algorithme est intéressante en soi et souvent utile avec le prototype utilisé ici puisque nous sommes limités à 11 états.
Dans l’exercice suivant, nous vous invitons à faire cette recherche, vous pourrez être étonné(e)s du petit nombre d’états nécessaires.

Différence de deux unaires

Exercice 8

Deux nombres X et Y non nuls sont écrits en unaire sur le ruban et séparés par un blanc.
La tête est sous le 1 de gauche de Y.
Établir un algorithme qui soustrait X à Y sachant que X<Y.

Multiplication de deux unaires

Exercice 9

Deux nombres X et Y sont écrits en unaire sur le ruban et séparés par un blanc.
La tête de lecture est située sous le chiffre de droite de X.
Établir un algorithme qui calcule le produit de X par Y.
La réponse sera écrite après un blanc à droite des 2 nombres.

Indication
Ajouter Y dans la réponse autant de fois qu’il y a des 1 dans X.

Pour remplacer trois 1 par trois 0 dans un nombre écrit en unaire, vous pouvez utiliser trois états.
En réitérant ce procédé autant de fois que c’est possible, vous pourrez connaître le quotient entier d’un unaire par le nombre 3.
Vous en trouverez une première application dans l’exercice qui suit.

Division euclidienne par 3 en unaire

Exercice 10

La tête de lecture est sous le chiffre de droite de l’unaire.
Établir un algorithme qui calcule le quotient et le reste de la division de l’unaire par trois.
Écrire le quotient à droite de l’unaire et le reste à sa gauche.

On ne peut pas appliquer la méthode précédente si on veut calculer, par exemple, le reste de la division par quinze car on ne dispose que de onze états.
Vous trouverez une bonne méthode dans l’exercice suivant.

Calculs modulo p

Exercice 11

On se donne des entiers N et p positifs non nuls.
La tête de lecture est sous le chiffre de gauche de p.
Établir un algorithme qui permet de calculer N modulo p.

Il peut être utile de savoir comparer deux nombres écrits en unaire sur le ruban. Vous en trouverez en particulier une application dans la recherche du PGCD de deux entiers qui sera proposée dans un prochain article.

Comparaison de deux unaires

Exercice 12

Deux nombres A et B sont écrits en unaire sur le ruban et séparés par une case blanche.
La tête de lecture est sous le blanc entre A et B.
Établir un algorithme qui détermine le plus petit des deux de la façon suivante :

• Si A≤ B, alors il écrit 0 à gauche des deux unaires ;
• Si A>B, alors il écrit 0 à droite des deux unaires.
  

L’algorithme devra terminer en remettant A et B sous leur forme initiale.

Nous avons vu comment recopier un unaire en remplaçant ses 1 par des 0 et terminer en remplaçant ses 0 par des 1 pour le retrouver. Mais on peut obtenir le même résultat en remplaçant les 1 par des blancs puis avec des déplacements précis retrouver exactement les 1 du nombre initial.
Vous allez pouvoir appliquer cela dans l’exercice qui suit.

Une application de l’addition en unaire

Exercice 13

Établir un algorithme du calcul des termes de la suite U_n = n en unaire.

Indication

Pour chaque U_n, le recopier à droite et lui ajouter 1.

Les calculs des termes d’une suite infinie correspondent à des machines de Turing qui ne s’arrêtent jamais.

Solutions des recherches du mois précédent

Exercice 14

Exercice 15

Exercice 16

Exercice 17

Prochain article :

Opérations et calculs avec des nombres écrits dans le système binaire.