Simulateur de machine de Turing

Observez une machine de Turing lire, écrire et se déplacer le long d'un ruban infini en suivant des règles de transition.

Exemple résolu — Simulateur de machine de Turing

Lire	'0'
Position de la tête	0

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Une seule bande rend les palindromes quadratiques 🖖

Le préréglage palindrome accepte 1,0,1,0,1 en 21 étapes et rejette 1,0,1,1 en 13. La machine ne peut pas comparer les deux extrémités en même temps : elle efface donc le symbole le plus à gauche, le garde dans son état, parcourt toute la bande pour vérifier celui de droite, l'efface et revient — une fois par paire. Pour une bande de n uns, ce programme prend exactement (n+1)(n+2)/2 étapes : 21 pour n = 5, 55 pour n = 9, 253 pour n = 21. Donnez une seconde bande à la même machine et la tâche devient linéaire ; Hennie a démontré en 1965 qu'avec une seule bande elle ne peut pas l'être. Le coût n'est ni dans l'alphabet ni dans le nombre d'états — il est dans le déplacement.

Comment quelques règles exécutent tout 🖖

Une machine de Turing n'a presque rien : un ruban, une tête qui lit une case et une courte table de règles. À chaque étape, elle ne regarde que son état courant et le symbole sous la tête, puis écrit un symbole, se déplace d'une case à gauche ou à droite et change d'état. Lancez le préréglage d'incrément binaire et observez-la glisser jusqu'au bout, puis reporter le +1 vers la gauche — exactement comme une addition posée.

Le castor affairé dépasse l'univers 🖖

Posez la plus petite question — combien de temps une machine minuscule peut-elle tourner avant de s'arrêter ? — et le calcul explose. Une machine à 5 états et 2 symboles avance exactement 47,176,870 pas avant de s'arrêter, une valeur démontrée seulement en 2024. À 6 états, le record connu dépasse déjà 2↑↑↑5, une tour de puissances qui éclipse chaque atome du cosmos. C'est pourquoi les simulateurs comme celui-ci plafonnent chaque exécution : une poignée d'états peut survivre à l'éternité.

Problème entièrement résolu

Configurations par lesquelles passe le programme palindrome sur 1 0 1 0 1 5 étapes
Le programme palindrome démarre sur le ruban 1 0 1 0 1, la tête sur la cellule 0, dans l'état q0. Dénombrez chaque configuration par laquelle il passe avant de s'arrêter — à partir de la table de règles, sans l'exécuter pas à pas — puis indiquez comment évolue ce décompte lorsque l'entrée s'allonge.
1. Lisez la table comme une suite de tours, et non comme une liste de déplacements. Une seule règle peut ouvrir un tour : q0 efface le symbole le plus à gauche et bifurque selon ce qu'il vient d'effacer, vers q1 pour un 1 et vers q2 pour un 0. Cette bifurcation constitue l'intégralité du mécanisme de comparaison. La machine ne stocke jamais le symbole sur le ruban ; elle le stocke dans l'état où elle se trouve, si bien que le comparer plus tard avec l'autre extrémité ne coûte aucun déplacement supplémentaire.
  
  $q_{0} : 1 \mapsto (_, R, q_{1}), 0 \mapsto (_, R, q_{2})$
2. Décomptez un tour sur un bloc de m symboles. Effacer l'extrémité gauche coûte 1 déplacement. La tête traverse ensuite les m − 1 symboles restants et effectue 1 déplacement supplémentaire sur la case blanche située au-delà pour faire demi-tour. Effacer l'extrémité droite coûte 1 déplacement, revenir en arrière sur les m − 2 survivants prend m − 2 déplacements, et 1 dernier déplacement sur la case blanche à l'extrémité gauche réoriente la machine vers la droite dans l'état q0.
  
  $1 + (m - 1) + 1 + 1 + (m - 2) + 1 = 2 m + 1$
3. Notre ruban fournit un bloc de 5, puis 3, puis un symbole unique — et un symbole unique ne constitue pas un tour. q0 l'efface, q1 franchit l'extrémité droite et se retourne, et q1c trouve un blanc là où devrait se trouver un partenaire. Un palindrome de longueur impaire possède un centre sans partenaire, et trouver ce blanc est ce qui valide l'acceptation.
  
  $m = 5 : 11, m = 3 : 7, m = 1 : 3$
4. Additionnez les trois, puis attention à l'erreur de piquet. 21 est le nombre de déplacements ; le transport dénombre les configurations, et 21 déplacements en visitent 22 dès lors que l'on inclut celle de départ.
  
  $11 + 7 + 3 = 21 ⟹ 21 + 1 = 22$
5. Généralisez à toute longueur impaire n. Les blocs vont de n à 3 en passant par n − 2, chacun coûtant 2m + 1, le centre coûtant 3. Sommer cette liste donne une expression quadratique en n, et non linéaire.
  
  $(2 n + 1) + (2 n - 3) + \dots + 7 + 3 = \frac{( n + 1 ) ( n + 2 )}{2}$
Réponse

22 configurations — 21 déplacements. La nature quadratique est l'élément essentiel à retenir. Un palindrome de 21 symboles coûte 253 déplacements : 12 fois plus de travail pour une entrée 4,2 fois plus longue. La raison est géométrique plutôt qu'astucieuse — les deux symboles comparés se trouvent toujours aux deux extrémités opposées de ce qu'il reste du ruban, et il n'y a qu'une seule tête, de sorte que chaque paire coûte une traversée complète du ruban restant. Donnez au système un second ruban et le même travail devient linéaire : recopiez l'entrée à mesure que vous la lisez, puis faites déplacer les deux têtes dans des directions opposées et comparez en une seule passe, soit environ 3n déplacements. Sur un seul ruban, il n'y a nulle part où placer cette copie, et les aller-retour sont inévitables.

$n = 5 : 21; n = 21 : \frac{22 \cdot 23}{2} = 253$

Références (3)

The single-tape quadratic lower bound for palindromes: F. C. Hennie, "One-tape, off-line Turing machine computations." Information and Control 8(6), 553–578, 1965.
Where multi-tape time complexity classes were set out: J. Hartmanis and R. E. Stearns, "On the computational complexity of algorithms." Transactions of the American Mathematical Society 117, 285–306, 1965.
The machine itself: A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society s2-42(1), 230–265, 1937.

Par l’équipe 42Math · Mis à jour 2026-06-19

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

Inversion de bits - Inversion de bits : échange les 0 et les 1
Binaire +1 - Incrémentation binaire : 1011→1100
1111 → 10000 - L'incrémentation peut recevoir la pire entrée possible : chaque bit vaut 1, la retenue doit donc tous les inverser. Observez-la balayer vers la droite jusqu'au blanc, revenir vers la gauche en changeant chaque 1 en 0, puis inscrire un nouveau 1 en tête sur une case qui ne faisait pas partie de l'entrée. Onze configurations au total, et le ruban ressort allongé d'une case.
Addition unaire m+n - Addition unaire : 3+2=5
1+1 = 2 - La somme unaire la plus simple qui soit, et elle requiert tout de même neuf configurations. La machine ne sait pas additionner. Elle efface un 1 du groupe de gauche, parcourt le ruban entier, puis ajoute un 1 à droite, une fois par unité. Le coût augmente avec la taille des nombres, pas avec la longueur de leur notation. Chargez le préréglage unaire plus long et comptez la différence.
Palindrome ✓ - Vérificateur de palindrome : 10101
1011 — rejeté - La paire externe correspond. La chaîne commence et finit par un 1, la machine efface donc les deux et revient pour traiter la couche interne. C'est seulement là qu'elle trouve un 0 face à un 1 et passe à l'état de rejet, l'affichage désignant la règle responsable. Un test de palindrome sur un seul ruban ne peut pas échouer prématurément. C'est précisément pourquoi chaque paire exige un balayage complet.

YouTube

The Rest Is Science·Alan Turing's Final Theory Was About Leopards