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[modifier | modifier le code]
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[modifier | modifier le code]
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é Σ [modifier | modifier le code]
Définition[modifier | modifier le code]
La fonction du castor affairé
Le score d'une machine de Turing M étant noté
Incalculabilité[modifier | modifier le code]
Dans son article de 1962, Tibor Radó prouve que si f : N → N est une fonction calculable, alors
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 à
Bien que
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,
Nombre maximal de pas[modifier | modifier le code]
En plus de la fonction
Tibor Radó a montré que S n'est pas calculable pour la même raison que
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,
- (« | | » étant la partie entière).
Exemples[modifier | modifier le code]
1 état[modifier | modifier le code]
Si la machine ne contient qu'un seul état (A), le castor affairé correspond à la table de transition suivante :
État | Symbole | |
---|---|---|
0 | 1 | |
A |
|
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
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[modifier | modifier le code]
Pour une machine à deux états (A et B), le castor affairé correspond à la table de transition suivante[6],[7],[1] :
État | Symbole | |
---|---|---|
0 | 1 | |
A |
|
|
B |
|
|
Cette machine s'arrête au bout de 6 pas, avec 4 1 écrits sur le ruban : S(2) = 6 et
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[modifier | modifier le code]
![](https://upload.wikimedia.org/wikipedia/commons/thumb/4/4b/State_diagram_3_state_busy_beaver_2B.svg/220px-State_diagram_3_state_busy_beaver_2B.svg.png)
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 | |
---|---|---|
0 | 1 | |
A |
|
|
B |
|
|
C |
|
|
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 | |
---|---|---|
0 | 1 | |
A |
|
|
B |
|
|
C |
|
|
Cette machine s'arrête au bout de 21 pas avec 5 1 sur le ruban.
On obtient donc S(3) = 21 et
4 états[modifier | modifier le code]
Pour une machine à quatre états, le castor affairé correspond à la table de transition suivante[6],[10] :
État | Symbole | |
---|---|---|
0 | 1 | |
A |
|
|
B |
|
|
C |
|
|
D |
|
|
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[modifier | modifier le code]
À 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 | |
---|---|---|
0 | 1 | |
A |
|
|
B |
|
|
C |
|
|
D |
|
|
E |
|
|
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[modifier | modifier le code]
Pour 6 états, la machine la plus active est la suivante [13] :
État | Symbole | |
---|---|---|
0 | 1 | |
A |
|
|
B |
|
|
C |
|
|
D |
|
|
E |
|
|
F |
|
|
Cette machine s'arrête après plus de étapes où est la notation des flèches de Knuth.
Autrement dit le nombre d'étapes qu'elle effectue avant de s'arrêter est de 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 × 1036534 é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 × 1036534 en base décimale est de 36534 tandis que le nombre de chiffres nécessaire pour écrire est bien plus grand que le nombre d'atomes 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]
Généralisation[modifier | modifier le code]
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],[16] :
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],[17].
Valeurs connues[modifier | modifier le code]
Les valeurs de
En 1964, Milton Green construit un ensemble de machines de Turing montrant que pour k ≥ 2 :
où est la notation des flèches de Knuth et A est la fonction d'Ackermann[18].
Ainsi :
(où le dernier terme est une tour de 327 = 7 625 597 484 987 exposants), et :
où g1 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
2 états | 3 états | 4 états | 5 états | 6 états | |
---|---|---|---|---|---|
2 symboles | 6 | 21 | 107 | ≥ 47 176 870 | ≥ |
3 symboles | 38 | ≥ 119 112 334 170 342 540 | ≥ 1,0 × 1014072 | ? | ? |
4 symboles | ≥ 3 932 964 | ≥ 5,2 × 1013036 | ? | ? | ? |
5 symboles | ≥ 1,9 × 10704 | ? | ? | ? | ? |
6 symboles | ≥ 2,4 × 109866 | ? | ? | ? | ? |
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 × 107036 | ? | ? |
4 symboles | ≥ 2 050 | ≥ 3,7 × 106518 | ? | ? | ? |
5 symboles | ≥ 1,7 × 10352 | ? | ? | ? | ? |
6 symboles | ≥ 1,9 × 104933 | ? | ? | ? | ? |
Références[modifier | modifier le code]
- (en) Tibor Radó, « On Non-Computable Functions », Bell Systems Technology Journal, vol. 41, no 3, , 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 »,
- (en) Heiner Marxen, « 2-state Busy Beaver (by T.Rado) »,
- (en) Heiner Marxen, « 3-state Busy Beaver (most ones) (by T.Rado) »,
- (en) Heiner Marxen, « 3-state Busy Beaver (most steps) (by T.Rado) »,
- (en) Heiner Marxen, « 4-state Busy Beaver (by A.Brady) »,
- (en) Heiner Marxen, « 5-state TM #1 from MaBu-List »,
- (en) Georgi Georgiev (Skelet), « Busy Beaver nonregular machines for class TM(5) »,
- (en) Sligocki, « BB(6, 2) > 10↑↑15 »,
- (en) Heiner Marxen, « 6-state 2-symbol #b (Pavel Kropitz) »,
- (en) Scott Aaronson, « The Busy Beaver Frontier », article, , p. 15 (lire en ligne [PDF])
- (en) Heiner Marxen, « 2-state 3-symbol currently best (by Brady / Michel) »,
- (en) Heiner Marxen, « 3-state 3-symbol #b (T.J. & S. Ligocki) »,
- (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, , p. 91-94 (DOI 10.1109/SWCT.1964.3)
- (en) Marxen Heiner, « Busy Beaver »,
Voir aussi[modifier | modifier le code]
Bibliographie[modifier | modifier le code]
- 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 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, no 162 (avril 1983), p. 647-665. Une preuve de = 13
Articles connexes[modifier | modifier le code]
Liens externes[modifier | modifier le code]
- (en) Busy Beaver (MathWorld)
- (en) Busy Beaver - Currently Known Results (Heiner Marxen)
- (en) Historical survey of Busy Beavers (Pascal Michel)