La machine de Turing

ou

Petite histoire de la construction d'un prototype d'ordinateur

Comment tout a commencé ?

Nous sommes en Juillet 2013 sur une plage dans l’île de Noirmoutier et mon fils ainé Olivier, professeur d'informatique à l'université de Clermont-Ferrand , me demande : "papa fais-moi une machine de Turing" !

Qu'est-ce que c'est ?

Ce que l'on appelle aujourd'hui "la machine de Turing" est un concept abstrait imaginé par le mathématicien anglais Alan Mathison TURING.

Quelle en est l'origine ?

En 1900 David Hilbert pose le problème de définir une méthode effectivement calculable pour décider si des équations diophantiennes ont des solutions.

Pour répondre à cette question, Alan Turing imagine un concept très simple qu'il présente dans une publication faite en 1936 à la London Mathematical Society intitulée: «Sur les nombres calculables avec une application au problème de la décision»

Les algorithmes ?

Cette publication décrit un système permettant de définir la notion d'algorithme et de préciser ce qu'est un nombre calculable. Nous savons tous maintenant à quel point les algorithmes sont dans toutes les applications informatiques et peuvent d'ailleurs éventuellement servir de bouc émissaire !

Quel est le système imaginé par Turing ?

Il est constitué de trois éléments :

• Un ruban infini contenant des cases dans lesquelles sont écrits des symboles.
• Un mécanisme appelé tête de lecture/écriture qui peut parcourir ce ruban en se déplaçant d'une case à droite ou à gauche, qui peut lire le symbole se trouvant au dessous et en écrire un autre éventuellement.
• Un registre des états qui permettent de donner des instructions à la machine.

Comment a été réalisé le prototype ?

Le prototype n'utilise que des composants qui existaient dans les années 30, principalement :

• Des circuits électriques
• Des contacteurs électriques
• Des moteurs électriques asservis par des systèmes de cames.
• Des relais électriques

Comment ça marche ?

Les symboles utilisés sont ici b, 0 et 1, le b (pour blanc) permet de laisser des espaces entre les chiffres.

On donne à la machine des instructions au moyen d'une table des transitions.

Par exemple, on voit sur cette table que si la machine est à l'état 2 et lit un b, elle devra écrire 1 se déplacer d'une case à gauche et passer à l'état 3.

Un système aussi simple peut-il faire des choses intéressantes ?

Oui et c'est une belle illustration de la puissance du principe imaginé par Turing, en voici quelques exemples :

• Établir une bijection entre les entiers et les points du plan de coordonnées entières.
• Vérifier la conjecture de Collatz
• Construire la suite de Fibonacci
• Calculer le PGCD de deux entiers
• Effectuer une division Euclidienne

Comment utiliser ce prototype?

Il se révèle une formidable outil pédagogique et je l'utilise en séances de recherche d'algorithmes auprès des étudiants qui peuvent voir leur algorithme s’exécuter pas à pas directement sur le prototype.

En attente de voir si la machine valide l'algorithme qu'ils ont imaginé !

Ou voir cette machine ?

• Sur le site internet : https://machinedeturing.com
• J'aurais le plaisir de vous la présenter lors de la conférence que je ferai au ZOOM à Laval le 6 Octobre 2023 à 18h30
  

Qui suis-je ?

Marc RAYNAUD professeur de mathématiques à la retraite.