Une machine de Turing réelle

Une équipe de 8 étudiants en première année de master au sein de département d’informatique (DI) de l’ENS de Lyon (Elie GEDEON, Anael GRANDJEAN, Thomas LAMBERT, Yannick LEO, Thomas LEVENTIS,  Robin PERROTIN, Etienne PYCIRCAN & Florent ROBIC) ont réalisé une machine de Turing entièrement mécanique. On ne parle pas ici de simuler une machine de turing car il est en effet très aisé de simuler une machine de Turing sur un ordinateur moderne. Il est bien question ici de relever le défit d’en construire une qui soit purement mécanique.  Ce fabuleux défi a été relevé en utilisant uniquement des éléments du jeux de construction LEGO™ : brique, engrenage, bielle, vérin pneumatique…


The Turing Machine Comes True par CNRS

Réaliser une machine de Turing relève à la fois du paradoxe et du rêve : paradoxe car il s’agit à partir d’éléments de base de construire et rendre concret une machine abstraite ; rêve de part la technologie ludique employée pour relever ce défit, sensation de retrouver la liberté de concevoir, construire, bâtir et de donner vie à une machine qui n’est en soit qu’un modèle abstrait du fonctionnement des ordinateurs et leur mémoire.

Description d’une machine de Turing

Cette machine fut inventée par A. Turing en 1936 afin de donner une définition précise au concept d’algorithme qu’il nommait “procédure mécanique”. A cette époque les ordinateurs sont encore très loin d’exister. Ce concept abstrait a pour but de définir une machine de façon la plus élémentaire possible et capable de mettre en oeuvre des mécanismes de calcul numériques ou symboliques. Une machine de Turing ressemble à une de vielle Remington à ruban sans touche… De façon très informelle ici (repris de wikipedia), une machine de Turing comprend :

  • Un « ruban » divisé en cases consécutives. Chaque case contient un symbole ou idéogramme parmi un alphabet fini (la réserve d’idéogrammes est finie). L’alphabet contient un symbole spécial « blanc » et un ou plusieurs autres symboles. Le ruban est lui supposé être de longueur infinie. En d’autres termes, on s’assure que la machine doit toujours avoir assez de longueur de ruban pour son exécution.
  • Une « tête de lecture/écriture » qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban. La machine ne peut voir son ruban infini qu’au travers d’une petite fenêtre qui ne découvre qu’une seule case de ce ruban. Ainsi, la machine est en mesure de décoder/reconnaitre l’idéogramme qui est dans la case, de l’effacer et d’en inscrire un autre pris dans la réserve finie d’idéogrammes.
  • Un « registre d’état » ou “état interne” qui mémorise l’état courant de la machine de Turing. Le nombre d’états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l’état initial de la machine avant son exécution. Jean-Gabriel Ganascia compare de façon amusante cet état interne à des « états d’âme » : ceux-ci conditionnent les réactions de la machine qui peut être « enjouée », et sauter gaiement d’une case à une autre du ruban, ou être « dépressive » et tout effacer sur son passage, ou encore être « mélancolique » et revenir indéfiniment sur son passé. A noter que la machine de Turing ne comporte qu’un nombre fini d’états internes
  • Une « table d’actions » qui indique à la machine quel symbole écrire, comment déplacer la tête de lecture et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l’état courant de la machine. Si aucune action n’existe pour une combinaison donnée d’un symbole lu et d’un état courant, la machine s’arrête. Cette table est ce que l’on appelle un programme de nos jours. En efeft, cela décrit pour chaque état interne, l’action exacte et déterministe que doit exécuter la machine.

La réalisation d’une machine de Turing en LEGO™

La réalisation a requis plus de 20.000 pièces LEGO™, soit 32 vérins, 1200 engrenages, 23 mètres d’axes, 24 leviers, et 50 mètres de tuyau, ainsi que des centaines d’heures de travail de conception et de montage. La machine reprend bien évidemment les grands composants définit ci dessus et s’articule en plusieurs parties :

  • Le chariot qui représente le ruban. Le chariot est composé d’une série de cases, et dans chaque case on peut y déposer un symbole qui sont représentés par les pièces jaunes. Caque pièce peut glisser dans sa case pour soit être la valeur 1 soit la valeur 0.

        

  • Le chariot peut se déplacer à gauche ou à droite grâce à un système de déplacement commandé par la machine

             

  • La tête de lecture qui est capable de déplacer les blocs de données et donc de mettre à 0 ou à 1 chaque case du ruban de la machine de Turing.

  • La mémoire qui mémorise l’état courant (et les états d’âme) de la machine de Turing.

  • Le grand ordonanceur qui active les différents composants à tour de rôle de la machine de Turing.

This entry was posted in En savoir plus. Bookmark the permalink.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>