la

Machine

de TURING









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:


1) multiplier par 2;

2) remplacer tous les 0 par des 1;

3) ajouter 1.







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:

- état indiquant une case vide;
- état indiquant une case avec 0;
- état indiquant une case avec 1.




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



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



Une table de décisions (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) et que c'est l'étape numéro 1 qui est exécutée la première.





É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. Ma "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 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 écrit en JavaScript. J'ai écrit ce petit programme, inclus dans cette page HTML, pour valider le contenu des tables de décisions "ajouter 1" (rappel: ajouter 1 à 111, à 110, à 101, à 1 et enfin à 0).





Organisation du ruban dans l'appli-cation développée avec JavaScript.