Simulateur de machine de Turing

Une machine de Turing est un modèle mathématique formel de calcul composé d'un ruban infini, d'une tête de lecture et d'une table de transition. Elle définit les limites de ce qui est calculable (thèse de Church-Turing). De façon statique, elle prouve l'indécidabilité du problème de l'arrêt, montrant qu'aucun algorithme ne peut prédire si un programme s'arrêtera.

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. Lance le préréglage d'incrément binaire et observe-la glisser jusqu'au bout, puis reporter le +1 vers la gauche — exactement comme une addition posée.

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é.