Alan TURING (1912-1954) fut un mathématicien britannique. Il a conçu en 1936 un modèle abstrait du fonctionnement des ordinateurs. Ce modèle porte le nom de Machine de TURING.

Presque 85 ans après (en 2020), son modèle est toujours le concept fondamental des ordinateurs actuels.

Note: les grandes qualités d'Alan TURING ont permis le décryptage d'une machine portable électro-mécanique appelée Énigma servant au chiffrement de messages. Conçue et réalisée par les allemands, Énigma permettait de chiffrer les ordres transmis par leurs états-majors lors de la deuxième guerre mondiale. Ce décryptage, conduit par Alan TURING, fut un exploit technique qui a certainement modifié l'issue de cette guerre.




1. Rappel sur la base binaire




26 (base 10) =  11010 (base 2)
49 (base 10) = 110001 (base 2)

2*26 = 52 =  110100
2*49 = 98 = 1100010

26 = 11010  = 11010
52 = 110100 = 110100

49 = 110001  = 110001
98 = 1100010 = 1100010

On note que n*2 (en base 2) = n||0

Rappel: || = concaténation

La section suivante décrit les éléments de la machine de TURING qui vont permettre de réaliser 3 pro-grammes (indépendants les uns des autres) sur un nombre binaire: 2. Les éléments de la Machine



Un ruban (illimité) divisé en cases (chaque case est une mémoire).



Une tête (fixe) de lecture/écriture.



Note: le ruban peut avancer ou reculer d'une seule case à la fois.



Une donnée (ici 26 en base 2) rangée à droite de la tête.



Un registre qui, dans l'exemple du nombre 26, fournira 3 états:





Une table de décisions (ci-dessus celle pour le programme de la multipication par 2).







Une table de décisions (ci-dessus celle pour le programme de remplacement des 0 par des 1).



Une table de décisions (ci-dessus celle pour le programme qui consiste à ajouter 1).


3. Pas à pas de la TdD "ajouter 1"

Exemple: 111 + 1 = 1000

(TdD = table de décisions)

Pour le bon fonctionnement de la machine, on considère ...

1) que la donnée doit être placée sur le ruban à droite de la fenêtre de lecture-écriture;

2) que l'éxécution de la table commence toujours par l'étape numéro 1.





Étape numéro 1: le ruban est déplacé vers la gauche tant qu'il y a des vides. Autrement dit: on positionne dans la fenêtre de lecture-écriture le chiffre le plus à gauche du nombre binaire. Et on saute à l'étape numéro 2.





Étape numéro 2: le ruban est déplacé vers la droite tant qu'il y a des 0 ou des 1 (donc tant qu'il n'y a pas de vides). Autrement dit: on positionne dans la fenêtre de lecture-écriture le chiffre le plus à droite du nombre binaire. Et on saute à l'étape numéro 3.





Étape numéro 3: tant que la fenêtre de lecture-écriture affiche 1 on le remplace par 0 et on déplace le ruban vers la droite. Si la fenêtre de lecture-écriture affiche un 0 on le remplace par un 1 et on arrête la machine. Si la fenêtre de lecture-écriture affiche un vide on le remplace par un 1 et on arrête la machine. Aussitôt l'arrêt effectué, on constate que la donnée du ruban est bien le résultat attendu.


4. Une Machine de TURING

4.1 En carton:




Ce petit montage en carton m'a permis de réaliser pas à pas la table de décisions du programme qui consistait à ajouter 1. Mon test a été réalisé sur les 5 exemples suivants: 111, 110, 11, 1 et 0:

• 111 + 1 = 1000
• 110 + 1 = 111
• 101 + 1 = 110
• 1   + 1 = 10
• 0   + 1 = 1


4.2 En vrai (un prototype):




La machine ci-dessus a été conçue et fabriquée par Marc RAYNAUD, professeur de mathématiques, à partir de circuits électriques, de moteurs Lego et de relais. Elle est précisément l’ordinateur imaginé par Alan TURING dans sa publication de 1936.

Une performance!

Marc RAYNAUD sillonne la France et même l’Angleterre avec sa belle machine pour des échanges pédagogiques autour du numérique et des mathématiques. Munie d’un ruban, de moteurs et de fils électriques, sa machine comprend les programmes écrits sur des fiches (papier) perforées.

Ci-contre un bouton pour aller sur le site de Marc RAYNAUD:

4.3 En JavaScript:

Ce qui suit (ci-dessous) n'est plus du HTML mais du JavaScript. C'est l'écho de l'exécution d'un programme que j'ai écrit en JavaScript. Inclus dans cette page HTML, ce programme m'a permis de valider le contenu de mes tables de décisions "ajouter 1" (rappel: ajouter 1 à 111, à 110, à 101, à 1 et enfin à 0).

Note: le code de mon programme écrit en JavaScript est dispo-nible en cliquant sur le bouton ci-contre:

Rangement interne de la table de décisions.

Chaque épape est un enregistrement divisé en 3 champs représentant les 3 états suivants:

--E-- désignant l'état vide (Empty)
--0-- désignant l'état 0
--1-- désignant l'état 1

Chaque état est divisé en 3 champs représentant les 3 actions suivan-tes: 1) w pour écrire (write) 0, 1 ou _ (vide); 2) d pour indiquer la direction du ruban( L pour Left ou gauche et R pour Right ou droite); 3) sss (step) pour désigner le numéro (sur 3 digits) de l'étape suivante (sss sera égal à 999 pour signifier la fin du traitement).

Dans mon algorithme JavScript, c'est le ruban qui se déplace (vers la gauche ou vers la droite) et la tête de lecture-écriture qui demeure fixe.

La donnée (ou les données) d'entrée est (sont) placée(s) sur le ruban, à droite de la tête de lecture-écriture.

Au départ, c'est l'étape numéro 1 de la table de décisions qui est exécutée. Un saut à l'étape numéro 999 correspond à la fin d'exécution de la table de décisions.
















5. Autres exemples:

À titre d'exemples, les exercices ci-dessous ont été réalisés avec "ma" Machine de TURING (écrite en Java-Script).

5.1 soustraire 1:
5.2 additionner: