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. De plus, à 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.

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

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 indiqué comme l'état de départ. Les états sont typiquement nommés 1, 2, …, n où 1 est l'état de départ, ou bien A, B, C, … où A est 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 :
  1. l'état en cours ;
  2. le symbole dans la cellule du ruban en cours de lecture ;

et retourne trois sorties :

1. le symbole à écrire par-dessus celui de la cellule en cours (éventuellement le même) ;
2. 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) ;
3. 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 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é, une machine de Turing possédant le score maximal. Celle-ci est un castor affairé à n états.

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

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 }. Comme les machines de Turing considérées décalent le ruban à chaque transition (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ó remarque que pour tout n, S(n) ≥ Σ(n), puisqu'un décalage est nécessaire pour écrire un symbole 1 sur le ruban. La fonction S croît donc au moins aussi rapidement que la fonction Σ.

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\lfloor {8n \over \ln n}\right\rfloor +c\right)}$ (« ${\displaystyle \lfloor \cdot \rfloor }$ » étant la partie entière).

Dans son article de 1962, Tibor Radó montre que si f : N → N est une fonction calculable, alors Σ(n) > f(n) pour tout n suffisamment grand. La fonction Σ n'est donc pas calculable ; par conséquent, la fonction S n’est pas calculable non plus^[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 > 5, bien que des bornes inférieures soient établies.

En 2016, Yedidia et Aaronson ont montré 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.

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, la machine la plus active connue s'arrête au bout de 38 pas, avec un ruban qui comporte alors 9 symboles autres que « 0 »^[6],[7].

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 alors 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],[8].

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

État	Symbole
	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.

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

État	Symbole
	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 symboles 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].

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

État	Symbole
	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 symboles 1 sur le ruban.

Contrairement au cas à 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 symboles 1^[6],[11],[1] :

État	Symbole
	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 symboles 1 sur le ruban.

On obtient donc S(3) = 21 et Σ(3) = 6, mais pour deux machines de Turing distinctes. Ces deux résultats sont décrits par Tibor Radó dès 1962^[1].

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

État	Symbole
	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 symboles 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 ...

Pour 5 états, le castor affairé est la machine suivante^[6],[13] :

État	Symbole
	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 symboles 1 en 47 176 870 pas. Les symboles 1 ne sont pas consécutifs : 8 191 symboles 0 sont intercalés.

Découverte en 1989, cette machine n'a été démontrée maximale qu'en 2024^[14].

À partir de 6 états, les castors affairés ne sont pas connus. Pour 6 états, la machine la plus active connue est la suivante, découverte en 2022 par Pavel Kropitz^[15] :

État	Symbole
	0	1
A	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état B	Écrire le symbole 0 Déplacer le ruban à gauche Passer à l'état D
B	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état C	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état F
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
D	Écrire le symbole 0 Déplacer le ruban à gauche Passer à l'état E	Écrire le symbole 1 Déplacer le ruban à droite Passer à l'état STOP
E	Écrire le symbole 1 Déplacer le ruban à gauche Passer à l'état F	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état B
F	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état C	Écrire le symbole 0 Déplacer le ruban à droite Passer à l'état E

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 ${\displaystyle 10^{10^{10^{.^{.^{.^{10}}}}}}}$ avec 15 itérations de puissance de 10.

Le précédent record était de 7,412 × 10^36 534 étapes^[16]. Pour avoir une idée d’à quel point ce précédent record est surpassé par le record actuel, il suffit de se dire que le nombre de chiffres nécessaire pour écrire 7,412 × 10^36 534 en base décimale est 36 535, tandis que celui nécessaire pour écrire ${\displaystyle 10\uparrow \uparrow 15}$ est ${\displaystyle (10\uparrow \uparrow 14)+1}$ ; or, rien que ${\displaystyle 10\uparrow \uparrow 3}$ vaut déjà ${\displaystyle 10^{10^{10}}}$= ${\displaystyle 10^{10\,000\,000\,000}}$.

Ce nouveau record a également surclassé les records précédemment connus pour 7, 8 et 9 états ; par conséquent, pour ces nombres d’états, les machines les plus actives actuellement connues sont de légères variations de la machine à 6 états ci-dessus, comme expliqué dans l'article de Scott Aaronson^[17].

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

En 1964, Milton Green construit un ensemble de machines de Turing qui montre que pour k ≥ 2 :

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

où ${\displaystyle \uparrow }$ est la notation des flèches de Knuth et A est la fonction d'Ackermann^[18].

Ainsi :

${\displaystyle \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 :

${\displaystyle \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 connues de S(n, m) et Σ(n, m) pour n et m ≤ 6^[19],[6]. Les entrées « ? » sont plus grandes que toutes celles à gauche ou au-dessus d’elles ; soit aucun résultat de recherche n’a été publié à leur sujet, soit des résultats publiés ont été rendus obsolètes par de meilleurs résultats obtenus pour des valeurs plus petites de n et m.

S(n,m)

	2 états	3 états	4 états	5 états	6 états
2 symboles	6	21	107	47 176 870	≥ ${\displaystyle 10\uparrow \uparrow 15}$
3 symboles	38	≥ 119 112 334 170 342 540	≥ 1,0 × 1014 072	?	?
4 symboles	≥ 3 932 964	≥ 5,2 × 1013 036	?	?	?
5 symboles	≥ 1,9 × 10704	?	?	?	?
6 symboles	≥ 2,4 × 109 866	?	?	?	?

Σ(n,m)

	2 états	3 états	4 états	5 états	6 états
2 symboles	4	6	13	≥ 4 098	?
3 symboles	9	≥ 374 676 383	≥ 1,3 × 107 036	?	?
4 symboles	≥ 2 050	≥ 3,7 × 106 518	?	?	?
5 symboles	≥ 1,7 × 10352	?	?	?	?
6 symboles	≥ 1,9 × 104 933	?	?	?	?

• 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 démontrant 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)

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