Machines de Turing avec CSS3

mardi 11 septembre 2012
par  Alain BUSSER

La machine de Turing est simulée avec un tableau à deux lignes : La première est formée de cases initialement vides que la machine de Turing colorie (la bande) et la seconde ligne du tableau est formée de cases toutes invisibles sauf une, représentant la position actuelle de la machine de Turing (et affichant au passage l’état actuel de celle-ci). Du code CSS en JavaScript permet de modifier l’aspect du tableau et donc de simuler les déplacements de la machine de Turing.

Exemple 1

La plus vieille machine de Turing connue a été inventée par Turing lui-même : Elle colorie alternativement les cases parcourues en bleu et rouge [1]. Pour la tester, il suffit de cliquer quelques fois sur le bouton idoine.

Machine de Turing

Si elle est dans l'état A

  • En voyant du blanc, elle passe à l'état B, peint du bleu et va vers la droite;

Si elle est dans l'état B

  • En voyant du blanc, elle passe à l'état A, peint du rouge et va vers la droite;

Algorithmes

Donc une machine de Turing peut être représentée en html par un tableau de deux lignes, dont la première rangée est formée de cellules d’identifiants respectifs a0, a1, a2 etc. (jusqu’à a24) et dont la seconde ligne est formée de cellules d’identifiants respectifs m0, m1, etc. Parmi les cellules de la seconde ligne, une seule est visible, celle où est censée se trouver la machine de Turing.

Secrets de fabrication

Pour fabriquer en html un tableau de 50 cellules munies de leurs identifiants, mieux vaut utiliser JavaScript. Dans le document le tableau dont les deux lignes ont pour identifiants respectifs « bande » et « machine » est juste décrit au minimum par le code html suivant :

<table>
        <tr id="bande">
        </tr>
        <tr id="machine"></tr>
</table>

Les cellules sont ajoutées l’une après l’autre dans ce tableau avec une fonction JavaScript lancée par la méthode « onLoad » de la page html. Dans une boucle sur n (allant de 0 à 24), on fait les opérations suivantes :

  • création d’une cellule (élément de type « td ») avec cell=document.createElement(’td’) (stockée dans une variable « cell ») ;
  • style de la bordure de cette cellule sur « trait plein, noir, de 1 pixel d’épaisseur », avec cell.style.border=’1px Black solid’ ;
  • dimensions de la cellule fixées à 16 pixels avec cell.style.width=’16px’ et cell.style.height=’16px’ ;
  • couleur de la cellule sur blanc avec cell.style.background=’White’ ;
  • affichage d’un caractère invisible (les cellules vides ne s’affichant pas sous Firefox), avec une couleur transparente cell.style.color=’rgba(0,0,0,0)’ et l’affichage dans cette couleur transparente, d’un point avec cell.innerHTML=’.’ ;
  • Attribution d’un identifiant variable à la cellule avec cell.id=’a’+n.toString() ;
  • Placement de cette cellule dans la première ligne du tableau avec document.getElementById(’bande’).appendChild(cell).

Ensuite, une suite d’opérations analogue est effectuée sur la cellule m0-m1-etc. avec

                cell=document.createElement('td');
                cell.id='m'+n.toString();
                cell.style.border='0px White solid';
                cell.style.width='16px';
                cell.style.height='16px';
                document.getElementById('machine').appendChild(cell);

Cette partie de la boucle crée 25 cellules invisibles dans la seconde ligne du tableau. Pour finir, l’une de ces cellules doit être rappelée à la réalité en lui donnant des propriétés CSS particulières : fond jaune, bord marron en relief de 3 pixels d’épaisseur, et affichage de l’état de la machine de Turing dans le cadre :

        robot=document.getElementById('m'+position.toString());
        robot.style.border='3px Brown outset';
        robot.style.background='Yellow';
        robot.innerHTML=etat;

La variable « etat » est une chaîne de caractères précédemment initialisée à « A » ; de même que la variable position est un entier préalablement initialisé dans le script.

Enfin la machine de Turing est décrite par un graphe pondéré, en fait un tableau associatif en JavaScript, comme par exemple pour la machine de Turing universelle du dernier onglet :

var Turing={"White" : {"A":"B Blue R","B":"A Red L"},
                        "Blue" : {"A":"A Red L","B":"B Red R"},
                        "Red" : {"A":"A Blue L","B":"A White R"}};

La machine de Turing lit la couleur de la cellule qui est au-dessus d’elle (une chaîne de caractères en CSS, portant le nom de la couleur en anglais) et, selon cette couleur et son état actuel, reçoit une chaîne de caractères portant trois mots : Son prochain état, la couleur qu’elle va peindre à la place de celle qu’elle vient de lire, et le sens de déplacement qu’elle va adopter (R ou L selon le sens).

Chaque changement d’état de la machine de Turing se fait lors du clic sur un bouton html, lequel est muni d’une méthode « onClick » (chaque fois qu’on clique le bouton, la fonction « jouer » est appelée) :

<button id="go" onclick="jouer();">Allez !</button>

Les opérations suivantes sont alors effectuées :

  • Si par exemple la variable « position » est égale à 8, le texte ’m’+position.toString() est égal à « m8 », ce qui est l’identifiant de la cellule où se trouve la machine de Turing ; cette cellule est récupérée dans la variable « ancien » avec ancien=document.getElementById(’m’+position.toString()) ;
  • La machine de Turing est alors rendue invisible avec ancien.style.background=’White’ et ancien.style.border=’0px White solid’ (fond blanc, bord blanc d’épaisseur nulle) ;
  • La cellule à lire (couleur déterminant l’évolution de la machine de Turing) est stockée dans la variable « actuel » avec actuel=document.getElementById(’a’+position.toString()) ;
  • La couleur portée par cette cellule est récupérée comme cinquième élément de son style CSS (actuel.style.background.split(’ ’)[5]) ; par exemple, si la cellule est blanche on aura le mot « White ».
  • L’entrée correspondant à cette couleur dans la description de la machine de Turing (tableau associatif) est un tableau associatif, dont l’entrée correspondant à l’état actuel de la machine de Turing (ancien.innerHTML) est lue. Par exemple, actions=Turing[actuel.style.background.split(’ ’)[5]][ancien.innerHTML].split(’ ’) transforme la chaîne de caractères « A Red L » en le tableau dont les trois entrées sont « A », « Red » et « L » ;
  • Maintenant qu’on n’a plus besoin de l’ancien état, on l’efface avec ancien.innerHTML=’’ ; « actions » contient alors un tableau comme [’A’,’Red’,’L’] ;
  • Le mouvement de la machine de Turing se fait en incrémentant ou décrémentant sa position selon que actions[2] soit égal à « R » ou « L » : if (actions[2]==’R’) position++ ; else position— ;  ; par exemple si la direction est « L » (comme « left ») la variable "position devient égale à 7 ;
  • On peint la cellule devant laquelle se trouve la machine de Turing, avec la couleur actions[1] : actuel.style.background=actions[1] (par exemple, en rouge) ;
  • Le changement d’état se fait avec etat=actions[0] (la variable « etat » est une variable globale) ;
  • on récupère la cellule devant laquelle se trouve actuellement la machine de Turing avec nouveau=document.getElementById(’m’+position.toString()) ; par exemple la cellule d’identifiant « m7 » est adressée ;
  • on modifie l’aspect de cette cellule en jouant sur ses propriétés CSS : nouveau.style.border=’3px Brown outset’ pour le cadre, nouveau.style.background=’Yellow’ pour la couleur de fond,
  • et nouveau.innerHTML=etat pour afficher (au milieu du cadre) l’état de la machine de Turing.

C’est en affichant une cellule auparavant invisible et en cachant l’ancienne cellule, qu’on simule le mouvement de la machine de Turing.

Le problème de l’arrêt

Les machines de Turing présentées ici sont atypiques en ce que leur bande est initialement vide, et qu’elles ne s’arrêtent jamais. Pour simuler l’arrêt d’une machine de Turing, il suffit de rajouter un état « H » qui ne possède aucune entrée dans le tableau associatif, ce qui, au moment où la machine s’arrête, va bloquer le programme JavaScript, avec un message d’erreur dans la console d’erreur (que personne ne regarde jamais de toute façon).

Une méthode plus « propre » mais plus longue consiste à mettre toute la fonction « jouer » dans un test comme if(etat !=’H’)...

Exemple 2

Un compteur en binaire. Chaque fois que la machine de Turing arrive tout à droite (retour à la case départ), un nombre entier est codé en binaire sur la bande (une case bleue représentant 0 et une case rouge représentant 1) :

Machine de Turing qui compte

Si on code les bleus par des 0 et les rouges par des 1, à chaque passage par la case tout à droite, la machine affiche un nombre en binaire, qui est un de plus que le précédent (1, 10, 11, 100, 101, etc).

Si elle est dans l'état A

  • En voyant du blanc, elle passe à l'état B, laisse du blanc et va vers la gauche;
  • En voyant du bleu, elle reste à l'état A, laisse du bleu et va vers la droite;
  • En voyant du rouge, elle reste à l'état A, laisse du rouge et va vers la droite;

Si elle est dans l'état B

  • En voyant du blanc, elle passe à l'état A, peint du rouge et va vers la droite;
  • En voyant du bleu, elle passe à l'état A, peint du rouge et va vers la droite;
  • En voyant du rouge, elle reste à l'état B, peint du bleu et va vers la gauche;

Exemple 3

Cet exemple était inconnu de Turing : La plus petite machine de Turing universelle [2], qui même sur une bande initialement vide, admet un comportement chaotique :

La machine de Turing (2,3) de Wolfram

C'est la plus petite des machines de Turing universelles (théorème d'Alex Smith). Ses deux états sont notés A et B, et la bande porte trois couleurs (le blanc initial, le bleu et le rouge).

Si elle est dans l'état A

  • En voyant du blanc, elle passe à l'état B, peint du bleu et va vers la droite;
  • En voyant du bleu, elle reste à l'état A, peint du rouge et va vers la gauche;
  • En voyant du rouge, elle reste à l'état A, peint du bleu et va vers la gauche;

Si elle est dans l'état B

  • En voyant du blanc, elle passe à l'état A, peint du rouge et va vers la gauche;
  • En voyant du bleu, elle reste à l'état B, peint du rouge et va vers la droite;
  • En voyant du rouge, elle passe à l'état A, peint du blanc (efface) et va vers la droite;


[1Dans son article, Turing lui faisait écrire des 0 et des 1 en alternance, ce qu’on peut aisément faire en remplaçant le CSS par des innerHTML.

[2c’est-à-dire capable de simuler toute autre machine de Turing convenablement codée au préalable sur sa bande


Documents joints

les sources en html
les sources en html
à regarder avec un éditeur de texte ou avec Firefox

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Raymond Smullyan

mercredi 15 mars

Le logicien Raymon Smullyan est décédé en février 2017, à l’âge respectable de 97 ans : Il avait eu Alonzo Church comme professeur ! Pour en savoir plus, voir cet article

Travailler à plusieurs

lundi 19 décembre 2016

Les enseignements d’exploration au lycée imposent aux enseignants de travailler ensemble. Chantal Tuffery-Rochdi a analysé dans sa thèse les pratiques des enseignants de MPS (méthodes et pratiques scientifiques). Elle répond aux questions des Cahiers pédagogiques.

Un document sur Eduscol

mardi 19 mai 2015

Un document clarifiant bien la façon dont les mêmes concepts vivent en mathématiques et dans les sciences « exactes » les utilisant, publié par Eduscol en octobre 2014. Citons-les :
« Le document proposé ci-dessous s’adresse aux professeurs de mathématiques, physique-chimie et sciences de l’ingénieur intervenant dans le segment [Bac-3 ; Bac+3]. Il vise à les informer des différences de présentation et d’interprétation qui sont faites de certains concepts mathématiques dans les autres disciplines. Ces éclaircissements peuvent contribuer à harmoniser et à clarifier l’utilisation de ces notions auprès des élèves. »

Histoire de la comptabilité

vendredi 28 décembre 2012

Sur ce site (en anglais) dédié à la comptabilité, on trouve des informations intéressantes sur l’histoire et les pratiques de ce domaine, qui peuvent être utiles aux professeurs enseignant des mathématiques financières (et aussi aux autres...).

La CGE et la réforme des lycées

lundi 16 janvier 2012

La Conférence des Grandes Écoles publie 19 préconisations pour la réforme du lycée.

Sur le Web : Les 19 préconisations

Pratique des mathématiques en série STD2A

lundi 16 janvier 2012

Le site de l’IGEN offre des recommandations et des ressources pour enseigner les mathématiques en série STD2A. Les thèmes abordés (couleurs et nuances de gris, arcs et architecture, jeux vidéos, photo et tableur, perspectives parallèles...) sont de nature à donner aussi des idées d’activités aux enseignants des autres séries !

En cheminant avec Kakeya

lundi 16 janvier 2012

Un livre (à télécharger) de Vincent Borelli et Jean-Luc Rullière qui présente le calcul intégral et la dérivation en s’appuyant sur la question de Kakeya. Pour les lycéens, les étudiants et tous les esprits curieux qui souhaitent voir les mathématiques sous un jour différent.

Sur le Web : Livre à télécharger

Bicentenaire Galois

lundi 12 septembre 2011

À l’occasion du bicentenaire de la naissance d’Évariste Galois (1811-2011), l’Institut Henri Poincaré et la Société mathématique de France organisent un ensemble de manifestations et proposent un site contenant diverses ressources documentaires susceptibles d’intéresser les enseignants.

Statistiques

Dernière mise à jour

mercredi 9 août 2017

Publication

760 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

403 aujourd'hui
530 hier
2074809 depuis le début
9 visiteurs actuellement connectés