La machine de Turing (2)

Utilisation du prototype pour étudier des algorithmes

Le 11 juin 2021  - Ecrit par  Marc Raynaud Voir les commentaires
É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 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 :

JPEG - 16.1 ko

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

JPEG - 246.6 ko

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

JPEG - 155.3 ko

Exercice 1

JPEG - 52.2 ko



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

Exercice 2

JPEG - 77.6 ko



Exercice 3

JPEG - 31.6 ko



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.

JPEG - 76.6 ko



Exercice 4

JPEG - 15.9 ko



Exercice 5

JPEG - 14.4 ko



Exercice 6

JPEG - 24.1 ko



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

JPEG - 3.3 ko

      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

JPEG - 34.8 ko

GIF - 1.5 ko

Addition unaire 1




Deuxième méthode

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



JPEG - 3.3 ko


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.

JPEG - 77.1 ko

GIF - 1.5 ko

Addition unaire 2




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.

JPEG - 4.7 ko


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.

GIF - 1.5 ko

Addition unaire complete





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

JPEG - 3.4 ko


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.

GIF - 1.5 ko

Soustraire 3 etats






Multiplication de deux unaires

JPEG - 4.1 ko

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
.

GIF - 1.5 ko

Multiplication en unaire






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

JPEG - 5 ko

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.

GIF - 1.5 ko

Division euclidienne




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

JPEG - 4.1 ko

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.

GIF - 1.5 ko

Calcul 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

JPEG - 8.1 ko

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.

GIF - 1.5 ko

Compare unaire




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

JPEG - 5.2 ko

Exercice 13

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

Indication

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

GIF - 1.5 ko

Suite Un=n unaire




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

JPEG - 20.7 ko

GIF - 1.5 ko

Exemple 5




Exercice 15

JPEG - 22.1 ko

GIF - 1.5 ko

x-y




Exercice 16

JPEG - 20.5 ko

GIF - 1.5 ko

Suite U n+1 =u n +2 en unaire




Exercice 17

JPEG - 43.9 ko

GIF - 1.5 ko

Division euclidienne





Prochain article :

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


Post-scriptum :

Un grand merci à tous.
Les remarques des relecteurs et les séances d’échange avec Ilia Itenberg, Jean-Michel Le Laouénan, Sébastien Kernivinen et Jean-Pierre Escofier sont très constructives et améliorent nettement la clarté de cet article.

Article édité par Ilia Itenberg

Partager cet article

Pour citer cet article :

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

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?