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;

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.

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

		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);

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

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.

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;

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;