Cette page ne fonctionne pas avec Internet Explorer.
Veuillez utiliser un autre navigateur.
Imaginée par Alan Turing en 1936, la machine de Turing est décrite par :
L'alphabet désigne les symboles qui peuvent être lus ou écrits sur le ruban. Dans cet exemple, l'alphabet est « 0 », « 1 » ou « ␣ » (case vide du ruban).
Le ruban, supposé infini, contient des cases, qui permettent de stocker chacune un unique symbole. Les options possibles sont :
Dans cet exemple, l'état initial du ruban contient les symboles « 1011 », à lire comme le nombre 11 en binaire.
Au démarrage de la machine, la case courante est positionnée sur le 1 le plus à gauche.
Dans cet exemple, les états sont : « État 1 », « État 2 » et « Fin ». Ils permettent à la machine de Turing de « se souvenir » de l'étape du traitement dans laquelle elle se trouve. Au démarrage, la machine est dans l'état « État 1 ». Elle se termine lorsqu'elle atteint l'état « Fin ».
La matrice de transition permet de déterminer ce qu'il faut écrire sur le ruban, quel doit être l'état suivant et dans quel sens déplacer le ruban, en fonction de l'état courant et de la lecture du ruban.
Dans cet exemple, la matrice est la suivante :
| État courant | Lu | Écrit | Déplacement de la case courante | État suivant |
|---|---|---|---|---|
| État 1 | 0 | 0 | Droite | État 1 |
| État 1 | 1 | 1 | Droite | État 1 |
| État 1 | ␣ | ␣ | Gauche | État 2 |
| État 2 | ␣ | 1 | Gauche | Fin |
| État 2 | 0 | 1 | Gauche | Fin |
| État 2 | 1 | 0 | Gauche | État 2 |
| Fin |
Il est possible de lancer la simulation avec le bouton « Démarrer », de faire du pas à pas avec « Pas à pas » et de la réinitialiser avec « Réinitialiser ».
La machine ajoute 1 à la valeur binaire 1011.
L'état « État 1 » permet de se déplacer jusqu'au chiffre le plus à droite, où il faut commencer à ajouter.
L'état « État 2 » permet d'ajouter 1 au chiffre courant. Il y a deux cas :