Alan Turing a publié en 1936 un article intitulé « On computable numbers, with an application to the Entscheidungsproblem ». Il y décrit un dispositif que l’on appelle « la machine de Turing », et que l’on peut représenter par le schéma suivant :

La machine est composée de :

un ruban infini comportant des cases dans lesquelles sont écrits des symboles

une tête de lecture/écriture qui peut :

• lire le symbole écrit dans la case au-dessus ;
• écrire ou non un autre symbole dans cette case ;
• se déplacer d’une case à gauche ou à droite ;
• changer d’état ;
  

un registre des états qui comprend un état initial 1 et un état final F qui provoque l’arrêt de la machine.

Ce que peut faire la machine dépend directement de l’état dans lequel elle est et du symbole lu.

Les instructions pour exécuter un algorithme sont données à la machine sous la forme d’une table des transitions comme ci-dessous :

Dans cette table, les trois symboles sont b, 0 et 1 ; elle se lit de la façon suivante :

• à l’état 1, si la machine lit un b, elle n’écrit rien, se déplace à gauche et ne change pas d’état ;
• à l’état 1, si la machine lit un 0, elle n’écrit rien et passe à l’état 2 ;
• à l’état 1, si la machine lit un 1, elle n’écrit rien et passe à l’état 2 ;
• à l’état 2, si la machine lit un b, elle passe à l’état final F qui provoquera son arrêt ;
• à l’état 2, si la machine lit un 0, elle écrit 1, se déplace à gauche et ne change pas d’état ;
• à l’état 2, si la machine lit un 1, elle écrit 0, se déplace à gauche et ne change pas d’état.
  

Vous retrouverez cette table dans cet article au niveau du traitement des chaînes de caractères, elle remplace les 0 par des 1 et les 1 par des 0.

Pour que la machine puisse la lire, la table des transitions est réalisée sous la forme d’une feuille perforée.

Une barre de soutien du mécanisme de lecture est la cause de la bande grise qui sépare les colonnes 3 et 4.


Voici le prototype réalisé pour matérialiser ce dispositif

Le « ruban infini » a été réalisé sous la forme d’un disque et les symboles sont des petits cylindres qui peuvent prendre 3 hauteurs différentes pour représenter b, 0 et 1 ( le b pour blanc correspond à l’absence d’écriture, il permet notamment de séparer deux nombres écrits sur le ruban comme dans la photo ci-dessous.)

Le registre des états est un contacteur rotatif à 12 positions.
L’état initial est l’état 1, un bouton poussoir permet de mettre ce contacteur à la position 1 avant de démarrer un nouveau programme.

L’état 12 est l’état final, il provoque l’arrêt de la machine et on ne peut pas lui donner des instructions. Ce prototype a donc 11 états utilisables.

Sachant qu’avec 2 ou 3 états, les possibilités de traitement d’algorithmes sont très limitées, j’ai cherché une solution technique pour augmenter ce nombre d’états.

Avec 11 états utilisables et 3 symboles, la feuille de programmation comprend 33 lignes.

Avec 3 colonnes pour le choix d’écriture (b, 0 ou 1), 2 colonnes pour le choix des déplacements (gauche ou droite) et 12 colonnes pour le choix d’un nouvel état, la feuille de programmation comprend 17 colonnes.

Avec 33 lignes et 17 colonnes, la feuille de programmation possède 561 cases et c’est ce nombre important de cases qui a déterminé le nombre d’états de ce prototype.

Pour chaque exercice, vous devrez établir une table des transitions de l’algorithme demandé.

A - Positionnement de la tête de lecture/écriture

La position de la tête de lecture/écriture est déterminante pour l’exécution d’un algorithme.

Nous allons voir dans cette première partie comment l’amener à l’emplacement voulu, dans un premier temps avec un seul état, puis avec plusieurs états.

Programmer un déplacement vers la droite

Au départ la tête est à l’état 1.
L’instruction est : si la lecture est un blanc, alors la tête se déplace d’une case vers la droite et elle reste à l’état 1.
Après avoir exécuté cette instruction, la tête est dans la même situation et l’instruction est toujours : si la lecture est un blanc, alors la tête se déplace d’une case vers la droite et elle reste à l’état 1.
On est donc dans une situation qui peut s’écrire :

et s’il n’y a que des blancs sur le ruban, ce mouvement ne s’arrêtera jamais.

Amener la tête sous le caractère de gauche

Il y a une suite de 1 sur le ruban et la tête est à gauche de cette suite, la machine doit placer la tête sous le premier 1.

On utilise le déplacement vers la droite vu ci-dessus auquel on ajoute une condition d’arrêt qui est ici : si la tête lit un 1, elle passe à l’état final et s’arrête.

Amener la tête sous le caractère de droite

La tête est sous le chiffre de gauche d’une séquence de 0 et de 1, la machine doit placer la tête sous le chiffre le plus à droite.

Ce cas se rencontrera souvent.
La tête parcourt toute la séquence :
tant qu’elle lit un 0 ou un 1, elle se déplace d’une case à droite.
Quand elle lit un blanc, il lui suffit de revenir sur ses pas d’une case à gauche pour être sous le chiffre de droite.

Exercice 1

La tête est sous le chiffre de droite d’une séquence de 0 et de 1.
La machine doit placer la tête sous le chiffre le plus à gauche.

Exercice 2

La tête est à gauche d’une séquence de 0 et de 1.
En se déplaçant vers la droite, la machine doit placer la tête sous le premier 1 rencontré.

Rejoindre la séquence et amener la tête sous le caractère de gauche

La tête est à droite d’une séquence de 0 et de 1, la machine doit placer la tête sous le chiffre le plus à gauche de la séquence.

Le déplacement vers la gauche se fait par l’état 1 avec comme condition de changement d’état la lecture d’un 0 ou d’un 1.

A l’état 2, elle parcourt la séquence en allant vers la gauche. Arrivée sur le premier blanc à gauche de cette séquence, elle revient sur ses pas d’une case vers la droite, passe à l’état final F et s’arrête.

Dans cette table, la lecture d’une case blanche donne un déplacement à gauche à l’état 1 et un déplacement à droite à l’état 2.

Si on doit donner deux instructions différentes pour la même lecture, il faut nécessairement au moins deux états.

Exercice 3

La tête est à gauche d’une séquence de 0 et de 1.
La machine doit placer la tête sous le premier blanc à droite de la séquence.

Exercice 4

La tête est à gauche d’une séquence de 0 et de 1.
La machine doit placer la tête sous le chiffre le plus à droite.

Il faut toujours s’assurer que la tête de lecture/écriture finira par stopper son déplacement !

Dans le cas de l’exercice 5, vous allez voir que 4 états sont suffisants pour cela.

Exercice 5

La tête est à gauche de 2 séquences séparées par des blancs.
La machine doit placer la tête sous le chiffre de droite de la deuxième séquence.

B - Traitement des chaînes de caractères

On ne peut pas écrire un caractère identique au caractère lu, c’est inutile et ce prototype ne le permet pas.

Remplacer les 0 par des 1 dans une chaîne de caractères

La tête doit parcourir la séquence de 0 et de 1 et remplacer les 0 par des 1.

La tête de lecture parcourt la séquence vers la droite de la façon suivante :

• quand elle lit un 0, elle écrit 1 et se déplace d’une case à droite.
  
• quand elle lit un 1, elle ne le change pas et se déplace d’une case à droite.
  
• Enfin, quand elle lit un blanc, c’est qu’elle a terminé, elle passe à l’état F et s’arrête.

  

  
  
  

Exercice 6

La tête est à droite d’une séquence de 0 et de 1.
La machine doit se déplacer jusqu’à la séquence et ensuite remplacer les 0 par des 1 et les 1 par des 0 et s’arrêter.

Exercice 7

La tête est à gauche d’une suite de 1.
La machine doit déplacer la séquence de la façon suivante :
effacer le 1 de gauche et écrire un 1 sur la première case blanche à droite de la séquence.

Déplacer successivement chaque 1 d’une case vers la droite.

Une suite de 1 est écrite sur le ruban. La tête est placée initialement sous le 1 de droite. On demande de déplacer successivement chaque 1 d’une case vers la droite.

C’est une action répétitive, elle peut être décrite par une boucle :

TANT QUE la tête lit 1
     - écrire b, se déplacer à droite et passer à l’état 2
     - écrire 1, se déplacer à gauche et passer à l’état 3
     - se déplacer à gauche et passer à l’état 1
Fin Tant Que
La tête passe à l’état final F.

Voici une illustration de l’exécution de la boucle principale

Les actions répétitives peuvent être décrites avec la boucle Tant Que ... Fin de Tant Que

Exercice 8

Une suite de 1 est écrite sur le ruban, la tête est placée initialement sous le 1 de droite.
On demande de déplacer successivement chaque 1 d’une case vers la gauche.

Exercice 9

La tête est sous le chiffre de droite.
On demande de déplacer d’une case vers la droite toute la chaîne de caractères.

Exercice 10

La tête est sous le chiffre de droite de la chaîne de droite.
On demande de concaténer les deux chaînes de caractères.

L’exercice 11 demande un peu plus de recherche.

Exercice 11

La tête est sous le chiffre de droite d’une suite de 1.
On demande de doubler le nombre d’éléments de cette suite en remplaçant chaque 1 par deux 0 et ensuite tous les 0 par des 1.

Comment savoir si le nombre de 1 est pair ou impair sans les compter ?

Exercice 12

La tête est sous le chiffre de gauche d’une chaîne de caractères.
On demande de déterminer la parité du nombre de 1 dans cette chaîne.
La tête de lecture devra parcourir la chaîne, passer une case et écrire la réponse : 0 pour pair et 1 pour impair.

Solutions des exercices proposés le mois précédent

Exercice 13

La tête est à gauche d’une séquence de 0 et de 1.
La machine doit placer la tête sous le deuxième blanc à droite de la séquence.

Exercice 14

La tête est à gauche d’une séquence de 0 et de 1.
Elle doit rejoindre cette séquence et remplacer les 0 par des 1.

Exercice 15

Deux suites de 1 séparées par un seul blanc sont écrites sur le ruban, la tête de lecture est sous le chiffre de gauche de la première suite.
On demande de concaténer les deux suites en déplaçant la suite de droite d’une case vers la gauche.

Exercice 16

La tête est sous le chiffre de gauche d’une suite de 1.
On demande de doubler le nombre de 1 de cette suite sans utiliser le 0.

Articles suivants :

Diagrammes de Turing, opérations et calculs en unaire et en binaire ;
applications intéressantes, comme la suite de Fibonacci, le calcul d’un PGCD ou encore la conjecture de Collatz.

Quelques mots sur Alan Turing

Alan Turing est né à Londres le 23 juin 1912, fils de Julius Mathison Turing et de Ethel Sara Stoney.

Ses parents partent aux Indes et le mettent en pension chez les Ward et le laissent plus de 10 ans en pension en Angleterre. Pendant ses études primaires, il est très brillant et inventif ; sa lecture du livre « Natural wonders every childs should know » de Edwin Brewster, lui montre le corps humain comme une gigantesque machine et il s’interroge sur les lois physiques, chimiques ou mathématiques qui permettent sa construction.

Durant l’été 1927, il étonne son professeur de mathématiques en lui présentant le développement en série infinie de la fonction arc tangente.

Il se lie d’amitié à un camarade Christopher Morcom, passionné de sciences et de mathématiques comme lui. Turing est profondément marqué par la mort de celui-ci (tuberculose bovine) en 1930.

En 1931, il est admis au King’s College de Cambridge ; il va alors s’intéresser à la logique mathématique, notamment sous l’influence de Max Newman et ses lectures, comme « The nature of the physical world » d’Arthur Eddington et « Mathematical foundations of quantum Mechanics » de John von Neumann, vont le questionner sur les notions de déterminisme et de complexité.

En 1900, David Hilbert pose 23 problèmes dont le 10e : peut-on trouver une méthode effectivement calculable pour démontrer qu’une équation diophantienne a des solutions.

En 1928, Kurt Gödel et Wilhelm Ackermann posent le problème de la décision (Entscheidungsproblem ) : peut-on trouver des « procédures mécaniques » permettant de décider si une proposition mathématique est valide ou non.

Alonzo Church et Alan Turing vont apporter par deux méthodes différentes une réponse négative à ce problème de la décision en logique du premier ordre.

En 1936, Alan Turing le fera en décrivant un système qui sera appelé par la suite la machine de Turing.

Cette machine est en fait le modèle le plus simple que l’on puisse concevoir et qui satisfait aux critères qui caractérisent un algorithme.

De 1937 à 1938, Turing est aux États-Unis et passe sa thèse à Princeton sous la direction d’Alonzo Church.

Pendant la guerre, à Bletchley Park dans la hutte 8, Alan Turing donne les idées essentielles pour le décryptage des messages allemands destinés à la marine et codés avec la machine Enigma.

Après la guerre, il participe à la conception du premier ordinateur ACE, mais il rejoindra finalement l’équipe qui développe le Ferranti Mark-I et sera l’un des premiers à le programmer.

Il s’intéressera ensuite à la morphogenèse, puis imaginera ce qu’on appelle le test de Turing : une personne pose des questions et doit déterminer si c’est un ordinateur ou un humain qui lui répond.

Sa fin est tragique : condamné pour homosexualité, il sera soumis à un traitement hormonal castrateur ; il finira par se suicider le 7 Juin 1954 à 42 ans en mangeant une pomme enduite de cyanure.

En 2013, 50 ans après sa mort, la reine d’Angleterre signe un acte royal de clémence déclarant que c’était une condamnation « que nous considérerions aujourd’hui comme injuste et discriminatoire ».
Turing va figurer sur les billets de 50 livres en 2022, cent dix ans après sa naissance.