Outils pour utilisateurs

Outils du site


start

Une machine de Turing

Par Olivier Bailleux, maître de conférences HDR à l'université de Bourgogne Franche Comté.

En résumé

Ce site présente une machine de Turing réalisée de manière artisanale à l'aide de briques de construction élémentaires, toutes identiques, elles mêmes constituées d'une bascule D et de quelques portes NAND.

Vous pouvez aussi découvrir cette réalisation en visionnant cette vidéo

(Cliquez ici si le premier lien ne fonctionne pas avec votre navigateur).

Pourquoi réaliser une machine de Turing ?

Alan Turing a imaginé cette machine en 1936 comme un concept abstrait. Elle n'était pas destinée à être physiquement réalisée mais à servir de base pour formaliser la notion de “procédure mécanique” de calcul et produire des résultat mathématiques qui sont toujours d'actualité aujourd'hui.

Réaliser physiquement une telle machine ne permet en aucun cas de concurrencer les ordinateurs actuels, qui sont basé sur une autre architecture dite de “Von Neumann”. Mais je pense qu'une telle réalisation est intéressante à plusieurs niveaux.

  1. Elle permet de concrétiser une notion abstraite, dans un esprit de vulgarisation scientifique.
  2. Elle montre que cette machine pouvant produire des comportements extrêmement complexes est effectivement réalisable à partir de composants élémentaires ayant individuellement des comportements très simples.
  3. Elle permet d’aborder et d'illustrer la notion de bonnes pratiques d'ingénierie : un système complexe se décompose en parties plus simples, dont les rôles sont bien identifiés. Chaque partie doit être conçue et testée avec un protocole rigoureux, les parties doivent être réalisée dans un ordre qui permet de les tester au fur et à mesure, en utilisant si applicable des éléments déjà réalisés et validés.
  4. C'est aussi une démarche artistique.

Qu'est-ce qu'une machine de Turing ?

C'est un ordinateur rudimentaire mais toutefois capable de calculer (sous réserve de disposer de ressources suffisantes) tout ce que peut calculer un ordinateur classique, ou même n'importe quelle autre machine connue, y compris par exemple un ordinateur quantique, ou même d'après une hypothèse connue sous le nom de thèse de Church-Turing, tout ce qui peut être calculé par tout procédé automatisable, y compris par des machines qui n'ont pas encore été inventées !

Dans sa déclinaison la plus simple (mais aussi générale que les variantes plus complexes), une machine de Turing est composée des éléments suivants :

  • une bande constituée de cellules pouvant contenir 0 ou 1,
  • une tête de lecture et écriture écriture pouvant lire et modifier la valeur de la cellule en face de laquelle elle se trouve,
  • un système permettant de déplacer la tête d’une position à la fois, vers la droite ou vers la gauche,
  • une mémoire d'état pouvant prendre un nombre fini de valeurs possibles (on parle de machines de Turing à 4 états, 5 états, etc.
  • un programme,
  • une unité de contrôle* le prenant en compte les instructions données par le programme pour déplacer la tête et écrire des valeurs sur la bande en fonction de l'état courant et de la valeur lue sur la bande.

Voici un exemple de programme simple qui recherche une séquence de deux valeurs 1 consécutive dans la partie de la bande située à droite de la position initiale de la tête de lecture.

État courant Valeur lue Valeur à écrire Sens de déplacement
100droite
111droite
200droite
211gauche

Ce programme exploite deux états de la machine plus l'état STOP qui provoque l'arrêt de l'exécution. On peut le représenter graphiquement comme ci-dessous.

Conception de la machine présentée

Briques de construction

Cette machine est essentiellement constituée de briques de construction toutes identiques qui sont les éléments constitutifs de la bande, de la tête de lecture / écriture et de l'unité de contrôle. Chaque brique est constituée d'une bascule D et de quelques portes NAND assurant des fonctions de multiplexage et démultiplexage.

Chaque brique est munie de deux LEDs permettant de visualiser sa valeur, à des fins pédagogiques : une LED bleue indique la valeur 0 et une LED rouge la valeur 1.

Organisation générale

La machine présentée dispose d'une bande de 12 cases qui peut être facilement étendue en ajoutant des briques de construction.C'est une machine à 6 états, mais là encore cette valeur peut être facilement augmentée par ajout de nouvelles briques.

La tête de lecture est constituée d'une rangée de 12 briques de construction montées en registre à décalage bidirectionnel.

La bande est constituée d'une rangée de 12 briques de construction représentant chacune une mémoire de 1 bit sélectionnée par le niveau 1 indiquant la position de la tête de lecture sur la bande.

L'unité de contrôle est composée de trois parties : à gauche, une brique mémorise pendant la durée d'un cycle de calcul la valeur lue sur la bande; à droite, trois briques montées en registre à décalage assurent la production de trois signaux d'horloge qui synchronisent les trois étapes d'un cycle de calcul (lecture, écriture, déplacement); au centre, 6 briques qui représentent chacune un des états possibles de la machine (l'état STOP étant géré séparément par la carte d'horloge).

Le programme est encodé par 12 blocs de 9 interrupteurs. Chaque bloc d'interrupteurs code une ligne de programme, active lorsque la machine se trouve dans un certain état et lit une certaine valeur sur la bande. Les interrupteurs ont respectivement les rôles suivants : nouvel état = 1, nouvel état = 2, …, nouvel état = 6, nouvel état = STOP, valeur à écrire sur la bande, sens de déplacement.

La carte d'horloge, en bas et à gauche, produit les signaux d'horloge et d'initialisation nécessairement au bon fonctionnement de la machine. Elle propose un mode automatique et un mode pas à pas. Elle assure aussi deux fonctionnalités qui facilitent les démonstrations : passage à l'état 1 si la tête de lecture tente de se déplacer à gauche de la première case de la bande, et passage à l'état STOP si elle tente de se déplacer à droite de la dernière case disponible. Cette carte peut être configurée pour réinitialiser la machine quelques secondes après l'arrêt d'un programme, de manière à enchaîner les exécution sans intervention extérieure. Cette carte horloge est réalisée à base de bascules D et de portes NAND à trigger de Schmitt.

Schéma d'ensemble

Le schéma suivant montre la manière dont les différentes briques de construction sont interconnectées. Cliquez sur la figure, puis ensuite à nouveau, pour obtenir une vue agrandie.

Un programme de démonstration

Le programme proposé a été choisi parce-que son fonctionnement est facile à comprendre et à suivre visuellement. Il a le défaut de ne s'arrêter que sur une machine à bande finie. On pourrait facilement réaliser un programme équivalent ayant la capacité de s'arrêter sur une machine à bande illimitée - en simulant une machine à alphabet ternaire comportant un symbole de séparation de données - mais un tel programme consommerait deux fois plus de bande et de temps à taille de donnée égale.

Ce programme a pour but de réaliser un des données présentes sur la bande en plaçant tous les 1 au début et tous les 0 à la suite. Voici sa représentation graphique.

Sa transcription sur la carte programme apparait ci dessous.

start.txt · Dernière modification: 2016/01/25 17:18 par admin