Castor affairé

Un castor affairé est, en théorie de la calculabilité, une machine de Turing qui maximise son « activité opérationnelle » (comme le nombre de pas effectués ou le nombre de symboles écrits avant son arrêt) parmi toutes les machines de Turing d'une certaine classe. Celles-ci doivent satisfaire certaines spécifications et doivent s'arrêter après être lancées sur un ruban vierge. Une fonction du castor affairé, ou fonction du nombre maximal de pas quantifie cette activité maximale pour une machine de Turing à n états ; ce type de fonction n'est pas calculable. En fait, à partir d'un certain point, cette fonction croît plus rapidement que n'importe quelle fonction calculable.

Déterminer le castor affairé parmi un ensemble de machines de Turing à n états donnés est un problème insoluble algorithmiquement ; en pratique, on ne peut même pas espérer exhiber un castor affairé pour un nombre n au-delà de 10.

Le concept, introduit en 1962 par le mathématicien hongrois Tibor Radó, est l'un des premiers exemples connus de fonction non calculable.

Nom

Le terme « castor affairé » est la traduction littérale de l'expression anglaise « busy beaver », désignant familièrement une personne industrieuse et travailleuse. Le terme (et le concept) est introduit en 1962 par Tibor Radó sous le nom « busy beaver game » (« jeu du castor affairé ») dans son article de 1962 « On Non-Computable Functions » (« Sur des fonctions non calculables »)[1].

Définition

Le jeu du castor affairé à n états, introduit par Tibor Radó, utilise une classe de machines de Turing dont chaque membre répond aux spécifications suivantes :

La machine possède n états plus un état spécial d'arrêt, où n est un nombre entier positif ; l'un des n états est défini comme l'état de départ. Ils sont typiquement nommés 1, 2, …, n, 1 étant l'état de départ, ou A, B, C, …, A étant l'état de départ.
Elle utilise un ruban unique, s'étendant à l'infini à droite et à gauche.
L'alphabet du ruban est {0, 1}, 0 servant de symbole vierge.
La fonction de transition de la machine prend en compte deux entrées :

l'état en cours ;
le symbole dans la cellule du ruban en cours de lecture ;

et retourne trois sorties :

le symbole à écrire par-dessus celui de la cellule en cours (éventuellement le même) ;
la direction de déplacement, à droite ou à gauche (c'est-à-dire l'action de déplacer le ruban d'une unité à gauche ou à droite de la cellule en cours) ;
l'état vers lequel placer la machine (éventuellement l'état d'arrêt).

La machine démarre sur une cellule quelconque d'un ruban complètement vierge (c'est-à-dire ne comportant que des 0) ; elle procède ensuite par itération de sa fonction de transition jusqu'à atteindre éventuellement l'état d'arrêt. Si, et seulement si la machine s'arrête, le nombre de 1 alors présents sur le ruban est appelé le score de la machine.

Le jeu du castor affairé consiste à trouver, pour un nombre n donné, la machine de Turing possédant le score maximal. Celle-ci est le castor affairé à n états.

Fonction du castor affairé Σ

Définition

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

Incalculabilité

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.

Nombre maximal de pas

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,

S(n)\leq \Sigma \left(n+\left\vert {8n \over \log(n)}\right\vert +c\right)

(« | | » étant la partie entière).

Exemples

1 état

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

État	Symbole
État	0	1
A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état STOP	Non utilisé

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

2 états

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

État	Symbole
État	0	1
A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état B	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état B
B	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état STOP

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 :

Pas	État initial	Symbole lu	Symbole écrit	Déplacement	État suivant	Ruban
1	A	0	1	Droite	B	… 0 0 0 1 0 0 0 …
2	B	0	1	Gauche	A	… 0 0 0 1 1 0 0 …
3	A	1	1	Gauche	B	… 0 0 0 1 1 0 0 …
4	B	0	1	Gauche	A	… 0 0 1 1 1 0 0 …
5	A	0	1	Droite	B	… 0 1 1 1 1 0 0 …
6	B	1	1	Droite	STOP	… 0 1 1 1 1 0 0 …

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

3 états

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] :

État	Symbole
État	0	1
A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état B	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état STOP
B	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état C	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état B
C	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état C	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état A

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] :

État	Symbole
État	0	1
A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état B	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état STOP
B	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état B	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état C
C	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état C	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état A

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

4 états

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

État	Symbole
État	0	1
A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état B	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état B
B	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état A	Écrire le symbole 0 Déplacer le ruban à gauche Passer à l'état C
C	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état STOP	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état D
D	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état D	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état A

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

5 états

À 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] :

État	Symbole
État	0	1
A	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état B	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état C
B	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état C	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état B
C	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état D	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état E
D	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état D
E	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état STOP	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état A

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

6 états

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

État	Symbole
État	0	1
A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état B	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état E
B	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état C	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état F
C	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état D	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état B
D	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état E	Écrire le symbole 0 Déplacer le ruban à gauche Passer à l'état C
E	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état A	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état D
F	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état STOP	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état C

Cette machine produit environ 3,515 × 10¹⁸²⁶⁷ 1 en environ 7,412 × 10³⁶⁵³⁴ pas. Elle est découverte en juin 2010.

Généralisation

Il est possible de généraliser le problème à des machines de Turing comportant n états et m symboles, conduisant aux fonctions généralisées suivantes :

Σ(n, m) : le nombre maximal de symboles autres que 0 écrits par une machine à n états et m symboles ;
S(n, m) : le nombre maximal de pas effectués par une machine à n états et m symboles.

Avec 2 états et 3 symboles, le castor affairé est la machine suivante, qui s'arrête au bout de 38 pas, son ruban comportant 9 symboles « 2 » (et 1 « 1 »)[6]^,[14] :

Avec 3 états et 3 symboles, la machine la plus active connue s'arrête au bout de 119 112 334 170 342 540 pas, son ruban contenant 374 676 383 exemplaires du même symbole. On ignore s'il s'agit du castor affairé pour cette combinaison d'états et de symboles[6]^,[15].

Valeurs connues

Les valeurs de Σ(n) et S(n) ne sont connues que pour n < 5. Pour toutes les autres ne sont connues, au mieux, que des bornes inférieures.

En 1964, Milton Green construit un ensemble de machines de Turning montrant que pour k ≥ 2 :

\Sigma (2k)>3\uparrow ^{k-2}3>A(k-2,k-2)

où $\uparrow$ est la notation des flèches de Knuth et A est la fonction d'Ackermann[16].

Ainsi :

\Sigma (10)>3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3^{3^{3}}=3^{3^{3^{.^{.^{.^{3}}}}}}

(où le dernier terme est une tour de 3²⁷ = 7 625 597 484 987 exposants), et :

\Sigma (12)>3\uparrow \uparrow \uparrow \uparrow 3=g_{1}

où g₁ est l'énorme valeur de départ de la suite qui définit le nombre de Graham.

Les tableaux suivants recensent les valeurs exactes et les bornes inférieures de S(n, m) et Σ(n, m) pour n et m ≤ 6[17]^,[6]. Les entrées « ? » sont plus grandes que le maximum des entrées à leur gauche ou au-dessus : elles n'ont pas donné lieu à des publications de recherche ou ont été surpassées par des machines plus petites.^[pas clair]

S(n,m)
	2 états	3 états	4 états	5 états	6 états
2 symboles	6	21	107	≥ 47 176 870	≥ 7,4 × 10³⁶⁵³⁴
3 symboles	38	≥ 119 112 334 170 342 540	≥ 1,0 × 10¹⁴⁰⁷²	?	?
4 symboles	≥ 3 932 964	≥ 5,2 × 10¹³⁰³⁶	?	?	?
5 symboles	≥ 1,9 × 10⁷⁰⁴	?	?	?	?
6 symboles	≥ 2,4 × 10⁹⁸⁶⁶	?	?	?	?

Σ(n,m)
	2 états	3 états	4 états	5 états	6 états
2 symboles	4	6	13	≥ 4 098	≥ 3,5 × 10¹⁸²⁶⁷
3 symboles	9	≥ 374 676 383	≥ 1,3 × 10⁷⁰³⁶	?	?
4 symboles	≥ 2 050	≥ 3,7 × 10⁶⁵¹⁸	?	?	?
5 symboles	≥ 1,7 × 10³⁵²	?	?	?	?
6 symboles	≥ 1,9 × 10⁴⁹³³	?	?	?	?

Références

(en) Tibor Radó, « On Non-Computable Functions », Bell Systems Technology Journal, vol. 41, n^o 3,‎ mai 1962, p. 877-884 (lire en ligne)
En fait, un argument plus simple (à la base de la démonstration de Radó) est que si cette question était décidable, il serait facile de résoudre le problème de l'arrêt.
suite A028444 de l'OEIS
The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me
metamath proof enumerators and other things
(en) Pascal Michel, « Historical survey of Busy Beavers », juin 2012
(en) Heiner Marxen, « 2-state Busy Beaver (by T.Rado) », 6 juillet 2010
(en) Heiner Marxen, « 3-state Busy Beaver (most ones) (by T.Rado) », 6 juillet 2010
(en) Heiner Marxen, « 3-state Busy Beaver (most steps) (by T.Rado) », 6 juillet 2010
(en) Heiner Marxen, « 4-state Busy Beaver (by A.Brady) », 6 juillet 2010
(en) Heiner Marxen, « 5-state TM #1 from MaBu-List », 6 juillet 2010
(en) Georgi Georgiev (Skelet), « Busy Beaver nonregular machines for class TM(5) », 16 mai 2003
(en) Heiner Marxen, « 6-state 2-symbol #b (Pavel Kropitz) », 6 juillet 2010
(en) Heiner Marxen, « 2-state 3-symbol currently best (by Brady / Michel) », 6 juillet 2010
(en) Heiner Marxen, « 3-state 3-symbol #b (T.J. & S. Ligocki) », 6 juillet 2010
(en) Milton W. Green, « A Lower Bound on Rado's Sigma Function for Binary Turing Machines », 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design,‎ 1964, p. 91-94 (DOI 10.1109/SWCT.1964.3)
(en) Marxen Heiner, « Busy Beaver », 7 novembre 2011

Voir aussi

Bibliographie

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 $\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 $\Sigma (4)$ = 13

Articles connexes

Liens externes

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

Portail de l’informatique
Portail de la logique
Portail des mathématiques
Portail des jeux

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[radó-1] (en) Tibor Radó, « On Non-Computable Functions », Bell Systems Technology Journal, vol. 41, n^o 3,‎ mai 1962, p. 877-884 (lire en ligne)

[2] En fait, un argument plus simple (à la base de la démonstration de Radó) est que si cette question était décidable, il serait facile de résoudre le problème de l'arrêt.

[oeis-3] suite A028444 de l'OEIS

[yedida-4] The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me

[nql-5] tamath proof enumerators and other things

[michel-6] (en) Pascal Michel, « Historical survey of Busy Beavers », juin 2012

[heiner_22-7] (en) Heiner Marxen, « 2-state Busy Beaver (by T.Rado) », 6 juillet 2010

[heiner_32_sigma-8] (en) Heiner Marxen, « 3-state Busy Beaver (most ones) (by T.Rado) », 6 juillet 2010

[heiner_32_s-9] (en) Heiner Marxen, « 3-state Busy Beaver (most steps) (by T.Rado) », 6 juillet 2010

[heiner_42-10] (en) Heiner Marxen, « 4-state Busy Beaver (by A.Brady) », 6 juillet 2010

[heiner_52-11] (en) Heiner Marxen, « 5-state TM #1 from MaBu-List », 6 juillet 2010

[skelet-12] (en) Georgi Georgiev (Skelet), « Busy Beaver nonregular machines for class TM(5) », 16 mai 2003

[heiner_62-13] (en) Heiner Marxen, « 6-state 2-symbol #b (Pavel Kropitz) », 6 juillet 2010

[heiner_23-14] (en) Heiner Marxen, « 2-state 3-symbol currently best (by Brady / Michel) », 6 juillet 2010

[heiner_33-15] (en) Heiner Marxen, « 3-state 3-symbol #b (T.J. & S. Ligocki) », 6 juillet 2010

[green-16] (en) Milton W. Green, « A Lower Bound on Rado's Sigma Function for Binary Turing Machines », 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design,‎ 1964, p. 91-94 (DOI 10.1109/SWCT.1964.3)

[heiner-17] (en) Marxen Heiner, « Busy Beaver », 7 novembre 2011