Machine de Turing : ruban, tête et règles

Une machine de Turing est un modèle très simple d’ordinateur, qui sert à définir ce qu’un ordinateur peut calculer. Elle a un ruban sans fin, une tête qui lit et écrit une case à la fois, et une table de règles.

Tout ce que calcule votre téléphone, une machine de Turing sait le calculer aussi, plus lentement. Vous allez suivre une machine qui ajoute 1 à un nombre binaire, puis la programmer.

Le ruban est une suite de cases, sans fin dans les deux sens. Chaque case contient un symbole, ou le symbole blanc _.

La tête est sur une case à la fois. À chaque pas, elle lit la case, puis applique la règle qui correspond à l’état et au symbole lu. Une règle dit trois choses : quoi écrire, de quel côté aller (G ou D), et quel est le nouvel état.

# Un seul pas de la machine "ajouter 1".
regles = {
    "droite,0": ["0", "D", "droite"],
    "droite,1": ["1", "D", "droite"],
    "droite,_": ["_", "G", "retenue"],
    "retenue,1": ["0", "G", "retenue"],
    "retenue,0": ["1", "G", "arret"],
    "retenue,_": ["1", "G", "arret"],
}
ruban = {0: "1", 1: "0", 2: "1", 3: "1"}
tete = 4
etat = "droite"
# Lire la case, appliquer la règle, bouger, changer d'état.
symbole = "_"
if tete in ruban:
    symbole = ruban[tete]
regle = regles[etat + "," + symbole]
ruban[tete] = regle[0]
if regle[1] == "D":
    tete = tete + 1
else:
    tete = tete - 1
etat = regle[2]
print("écrit", regle[0], "- tête en", tete, "- état", etat)
# Mettez tete = 3 et etat = "retenue", puis relancez.

La machine « ajouter 1 » s’arrête toujours : la retenue finit par trouver un 0 ou un blanc. Ce n’est pas vrai de toute machine.

Si une règle renvoie la tête vers la droite sans jamais changer d’état, elle avance pour toujours. Le tableau compare trois machines. Savoir à l’avance si une machine s’arrête est le sujet de la leçon suivante.

Tout ce qu’on sait calculer avec un langage comme Python, une machine de Turing le calcule aussi, et l’inverse est vrai. Aucun ordinateur connu n’a dépassé ce modèle.

On appelle cela la thèse de Church-Turing. C’est une idée acceptée, pas un théorème, car « calculable » est une notion de la vie courante.

Le labo ne contient pas de machine de Turing, mais ses outils lisent n’importe quelle table écrite en texte. Le premier Run écrit les six règles de « ajouter 1 » dans un fichier, une règle par ligne, les cinq champs séparés par une espace.

Les suivants comptent les lignes, cherchent un état et listent les états de départ. Le dernier montre qu’un nombre de Python n’a pas de limite fixe.

printf '%s\n' 'droite 0 0 D droite' 'droite 1 1 D droite' 'droite _ _ G retenue' 'retenue 1 0 G retenue' 'retenue 0 1 G arret' 'retenue _ 1 G arret' > ~/regles.txt

wc -l < ~/regles.txt

grep -c "retenue" ~/regles.txt

cut -d' ' -f1 ~/regles.txt | sort -u

python3 -c "print(2 ** 200)"

Écrivez la table d’une machine qui efface tous les 1 du ruban, puis s’arrête sur le premier blanc. Combien de pas faut-il pour le mot 111 ?

Écrivez ensuite une machine qui ne s’arrête jamais avec une seule règle. Vérifiez-la avec votre fonction et un maximum de 50 pas.