Castor affairé

La fonction du castor affairé Σ : N → N est définie telle que Σ(n) est le score maximal parmi toutes les machines de Turing à 2 symboles et n états répondant aux spécifications énoncées dans le paragraphe précédent, lorsqu'elles débutent sur un ruban vierge.

Σ est une fonction bien définie : pour chaque n, il existe un nombre fini de machines de Turing à n états définies ainsi, à un isomorphisme près, et donc un nombre fini de temps d'exécution possibles.

Le score d'une machine de Turing M étant noté σ(M), toute machine de Turing à 2 symboles et n états pour lequel σ(M) = Σ(n) est appelée un castor affairé. Pour un n donné, le castor affairé n'est pas unique : il en existe au moins deux ; si M est un castor affairé, il suffit de changer le sens de déplacement du ruban lors d'une transition vers l'état d'arrêt pour obtenir un autre castor affairé.

Dans son article de 1962, Tibor Radó prouve que si f : N → N est une fonction calculable, alors Σ(n) > f(n) pour tout n suffisamment grand. Σ n'est donc pas une fonction calculable[1].

Ceci implique qu'il est indécidable par un algorithme général de déterminer si une machine de Turing arbitraire est un castor affairé : un tel algorithme ne peut pas exister puisque son existence permettrait à Σ d'être calculée, ce qui est impossible[2].

Bien que Σ soit une fonction incalculable, il est possible de déterminer sa valeur pour des petites valeurs de n. On peut montrer sans problème que Σ(0) = 0, Σ(1) = 1 et Σ(2) = 4, et avec plus de difficulté que Σ(3) = 6 et Σ(4) = 13[3]. Σ(n) n'est pas connue pour n > 4, bien que des bornes inférieures soient établies.

En 2016, Yedidia et Aaronson ont prouvé qu'une machine de Turing à 7 918 états pouvait énumérer l'ensemble des preuves déductibles dans l'axiomatique ZFC, s'arrêtant si une contradiction était trouvée[4]. Par application du second théorème d'incomplétude de Gödel, Σ(7 918) est incalculable (en n'utilisant que les axiomes de ZFC). Cette borne supérieure sur la calculabilité de Σ a par la suite été rabaissée à 1 919[5], en construisant une machine similaire pour l'axiomatique ZF.

En plus de la fonction Σ, Tibor Radó introduit la fonction du nombre maximal de pas S. Pour une machine de Turing M de l'ensemble E_n des machines de Turing à 2 symboles et n états définies plus haut, s(M) est le nombre de décalages de ruban que M exécute avant de s'arrêter. S(n) est alors le nombre maximal de décalages pour E_n : S : n ↦ max { s(M) | M ∈E_n }. Ces machines de Turing décalant le ruban à chaque transition ou « pas » (y compris dans une transition vers l'état d'arrêt), ce nombre maximal de décalages est également le nombre maximal de pas.

Tibor Radó a montré que S n'est pas calculable pour la même raison que Σ ne l'est pas : elle croît plus rapidement que toute fonction calculable. Il remarque que pour tout n, S(n) ≥ Σ(n), puisqu'un décalage est nécessaire pour écrire un 1 sur le ruban. S croît donc au moins aussi rapidement que Σ, laquelle croît déjà plus rapidement que n'importe quelle fonction calculable.

Les inégalités suivantes sont valides pour tout n ≥ 1 :

• S(n) ≥ Σ(n)
• S(n) ≤ (2n-1).Σ(3n+3)
• S(n) < Σ(3n+6)
• Il existe une constante c telle que, pour tout n ≥ 2,

${\displaystyle S(n)\leq \Sigma \left(n+\left\vert {8n \over \log(n)}\right\vert +c\right)}$ (« | | » étant la partie entière).

Si la machine ne contient qu'un seul état (A), le castor affairé correspond à la table de transition suivante :

À partir d'un ruban vierge, cette machine lit tout d'abord le symbole 0 : elle écrit donc le symbole 1, déplace le ruban à droite et s'arrête. On obtient donc S(1) = 1 et Σ(1) = 1.

Le résultat serait identique si le ruban était déplacé à gauche plutôt qu'à droite. Si la machine restait à l'état A après le déplacement du ruban, elle recommencerait le même processus et ne s'arrêterait jamais. Dans tous les cas, la valeur de la table de transition pour le symbole 1 n'a aucune importance, une telle machine ne pouvant jamais atterrir sur une cellule contenant ce symbole.

Pour une machine à deux états (A et B), le castor affairé correspond à la table de transition suivante[6] - [7] - [1] :

Cette machine s'arrête au bout de 6 pas, avec 4 1 écrits sur le ruban : S(2) = 6 et Σ(2) = 4.

Le tableau suivant donne le détail de ses opérations, en partant d'une bande vierge et d'un état initial A :

La colonne « Ruban » donne l'état du ruban après une opération ; le caractère qui vient d'être écrit est en gras, celui sur lequel se trouve la tête de lecture de la machine est souligné.

La direction du déplacement lors de la dernière opération n'a pas d'importance, la machine s'arrêtant de toute façon.

Si on inversait toutes les directions dans la table de transition (« droite » à la place de « gauche » et réciproquement), on obtiendrait également un castor affairé, la machine se comportant exactement en miroir de celle décrite ci-dessus.

Cette machine, très simple, est déjà décrite par Tibor Radó dans son article initial de 1962[1].

Représentation comme automate fini du castor affairé à trois états produisant le plus de « 1 ». Chaque cercle correspond à un état, chaque flèche à une transition. Le label de chaque flèche donne le symbole lu et le résultat ; par exemple, « 0/P,R » indique que le symbole « 0 » est lu, qu'on écrit sur le ruban (print, soit « P ») et qu'on se déplace à droite (right, « R »).

Pour une machine à trois états (A, B et C), le castor affairé produisant le plus de 1 correspond à la table de transition suivante[6] - [8] - [1] :

Cette machine s'arrête au bout de 14 pas avec 6 1 sur le ruban.

Contrairement au cas avec 2 états, cette machine n'est pas celle qui s'arrête au bout du plus grand nombre de pas. Il en existe une autre qui est le castor affairé produisant le plus de pas, mais qui produit moins de 1[6] - [9] - [1] :

Cette machine s'arrête au bout de 21 pas avec 5 1 sur le ruban.

On obtient donc S(3) = 21 et Σ(3) = 6, mais pour deux machines de Turing distinctes. Ce résultat est décrit par Tibor Radó dès 1962[1].

Pour une machine à quatre états, le castor affairé correspond à la table de transition suivante[6] - [10] :

Cette machine s'arrête au bout de 107 pas avec 13 1 sur le ruban. Ceux-ci ne sont pas consécutifs, l'état final du ruban étant le suivant : ... 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 ...

À partir de 5 états, les castors affairés ne sont pas connus. Pour 5 états, la machine la plus active est la suivante[6] - [11] :

Cette machine produit 4 098 1 en 47 176 870 pas. Les 1 ne sont pas consécutifs : 8 191 0 sont intercalés. Découverte en 1989, on ignore s'il s'agit du castor affairé pour cette classe de machine de Turing : en 2003, il subsistait 43 machines de ce type dont la possible exécution perpétuelle n'était pas prouvée[12].

Pour 6 états, la machine la plus active est la suivante [13] :

Cette machine s'arrête après plus de ${\displaystyle 10\uparrow \uparrow 15}$ étapes où ${\displaystyle \uparrow }$ est la notation des flèches de Knuth.

Autrement dit le nombre d'étapes qu'elle effectue avant de s'arrêter est de ${\displaystyle 10^{10^{10^{.^{.^{.^{10}}}}}}}$avec 15 itérations de puissance de 10.

Cette machine a été découverte en 2022 par Pavel Kropitz.

Le précédant record était de 7,412 × 10³⁶⁵³⁴ étapes[14].

Pour avoir une idée à quel point ce nouveau record est plus grand que l'ancien, il suffit de se dire que le nombre de chiffres nécessaire pour écrire 7,412 × 10³⁶⁵³⁴ en base décimale est de 36534 tandis que le nombre de chiffres nécessaire pour écrire ${\displaystyle 10\uparrow \uparrow 15}$ est bien plus grand que le nombre d'atome dans l'univers.

Ce nouveau record est si grand qu'il a aussi remplacé les valeurs précédentes des machines de Turing à 7,8 et 9 états qui sont aujourd'hui des légères variations de cette machine comme expliqué dans l'article de Scott Aaronson [15]

• Lin, Shen and Radó, Tibor (1965), Computer Studies of Turing Machine Problems, Journal of the ACM, Vol. 12, No. 2 (avril 1965), p. 196-212. Ceci inclut la thèse de Lin, qui a montré que ${\displaystyle \Sigma (3)=6}$ en prouvant que toutes les machines à trois états et deux symboles ne s'arrêtaient jamais si elles ne s'arrêtent pas après 21 étapes.
• Brady, Allen H. (1983), The determination of the value of Rado's noncomputable function Sigma(k) for four états Turing machines, Mathematics of Computation, vol. 40, n^o 162 (avril 1983), p. 647-665. Une preuve de ${\displaystyle \Sigma (4)}$ = 13

• Machine de Turing
• Complexité de Kolmogorov
• Turmite

• (en) Busy Beaver (MathWorld)
• (en) Busy Beaver - Currently Known Results (Heiner Marxen)
• (en) Historical survey of Busy Beavers (Pascal Michel)