Voir la source de Castor affairé

{{homonymes|Castor}}

Un '''castor affairé''' est, en [[Calculabilité|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'[[Problème de l'arrêt|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 [[Fonction calculable|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 [[Calculabilité|fonction non calculable]].

== Nom ==
Le terme « [[Castor (genre)|castor]] affairé » est la traduction littérale de l'expression anglaise « ''{{langue|en|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 « ''{{langue|en|busy beaver game}}'' » (« jeu du castor affairé ») dans son article de 1962 « ''{{Langue|en|On Non-Computable Functions}}'' » (« Sur des fonctions non calculables »)<ref name="radó" />.

== Définitions ==

=== Machines de Turing considérées ===
Le jeu du castor affairé à ''n'' états, introduit par Tibor Radó, utilise une classe de [[Machine de Turing|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 {{nobr|{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 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.

=== Fonction du castor affairé Σ ===

La fonction du castor affairé Σ : '''[[Entier naturel|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é.

=== Nombre maximal de pas ''S'' ===
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<sub>n</sub>'' 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<sub>n</sub>'' : ''S'' : ''n'' ↦ max { ''s''(''M'') | ''M'' ∈''E<sub>n</sub>'' }. 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'') ≤ (2''n''-1).Σ(3''n''+3)
* ''S''(''n'') < Σ(3''n''+6)
* Il existe une constante ''c'' telle que, pour tout ''n'' ≥ 2,
:<math>S(n) \leq \Sigma \left( n + \left\lfloor {8n \over \ln n}\right\rfloor + c \right)</math> (« <math>\lfloor\cdot\rfloor</math> » étant la [[Partie entière et partie fractionnaire|partie entière]]).

== Incalculabilité ==
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<ref name="radó" />.

Ceci implique qu'il est [[Décidabilité|indécidable]] par un [[Algorithmique|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<ref>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]].</ref>.

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<ref name="oeis" />. Σ(''n'') n'est pas connue pour ''n'' > 5, bien que des [[Borne inférieure|bornes inférieures]] soient établies.

En 2016, Yedidia et [[Scott Aaronson|Aaronson]] ont montré qu'une machine de Turing à {{nombre|7918}} états pouvait énumérer l'ensemble des preuves déductibles dans l'axiomatique [[Théorie des ensembles de Zermelo-Fraenkel|ZFC]], s'arrêtant si une contradiction était trouvée<ref name="yedida">[https://www.scottaaronson.com/blog/?p=2725 The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me]</ref>. Par application du [[Théorèmes d'incomplétude de Gödel|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<ref name="nql">[https://github.com/sorear/metamath-turing-machines metamath proof enumerators and other things]</ref>, en construisant une machine similaire pour l'axiomatique ZF.

== Généralisation à ''m'' symboles ==
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 »<ref name="michel" />{{,}}<ref name="heiner_23" />.

Avec 3 états et 3 symboles, la machine la plus active connue s'arrête au bout de {{formatnum:119112334170342540}} pas, son ruban contenant alors {{formatnum:374676383}} exemplaires du même symbole. On ignore s'il s'agit du castor affairé pour cette combinaison d'états et de symboles<ref name="michel" />{{,}}<ref name="heiner_33" />.

== Exemples ==

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

{| class="wikitable"
|-
! rowspan="2" | État
! colspan="2" | Symbole
|-
! 0 !! width="50%" | 1
|-
! A
| 
* Écrire le symbole '''1'''
* Déplacer le ruban à '''droite'''
* Passer à l'état <span style="color:blue">'''STOP'''</span>
| align="center" | ''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<ref name="michel" />{{,}}<ref name="heiner_22" />{{,}}<ref name="radó" /> :

{| class="wikitable"
|-
! rowspan="2" | État
! colspan="2" | Symbole
|-
! 0 !! width="50%" | 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 <span style="color:blue">'''STOP'''</span>
|}

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

{| class="wikitable" style="text-align: center"
|-
! Pas
! État<br>initial
! Symbole<br>lu
! Symbole<br>écrit
! Déplacement
! État<br>suivant
! Ruban
|-
! 1
| A || 0 || 1 || Droite || B || … 0 0 0 '''1''' {{Souligner|0}} 0 0 …
|-
! 2
| B || 0 || 1 || Gauche || A || … 0 0 0 {{Souligner|1}} '''1''' 0 0 …
|-
! 3
| A || 1 || 1 || Gauche || B || … 0 0 {{Souligner|0}} '''1''' 1 0 0 …
|-
! 4
| B || 0 || 1 || Gauche || A || … 0 {{Souligner|0}} '''1''' 1 1 0 0 …
|-
! 5
| A || 0 || 1 || Droite || B || … 0 '''1''' {{Souligner|1}} 1 1 0 0 …
|-
! 6
| B || 1 || 1 || Droite || STOP || … 0 1 '''1''' {{Souligner|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<ref name="radó" />.

=== 3 états ===
[[Fichier:State diagram 3 state busy beaver 2B.svg|thumb|Représentation comme [[automate fini]] du castor affairé à trois états produisant le plus de symboles « 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 »).

Remarque : cet automate ne correspond pas à la machine de Turing à 3 états ci-contre (bien qu'il produise effectivement 6 symboles 1, mais au bout de 13 pas seulement...)]]
Pour une machine à trois états ('''A''', '''B''' et '''C'''), le castor affairé produisant le plus de '''1''' correspond à la table de transition suivante<ref name="michel" />{{,}}<ref name="heiner_32_sigma" />{{,}}<ref name="radó" /> :

{| class="wikitable"
|-
! rowspan="2" | État
! colspan="2" | Symbole
|-
! 0 !! width="50%" | 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 <span style="color:blue">'''STOP'''</span>
|-
! 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'''<ref name="michel" />{{,}}<ref name="heiner_32_s" />{{,}}<ref name="radó" /> :

{| class="wikitable"
|-
! rowspan="2" | État
! colspan="2" | Symbole
|-
! 0 !! width="50%" | 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 <span style="color:blue">'''STOP'''</span>
|-
! 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<ref name="radó" />.

=== 4 états ===
Pour une machine à quatre états, le castor affairé correspond à la table de transition suivante<ref name="michel" />{{,}}<ref name="heiner_42" /> :

{| class="wikitable"
|-
! rowspan="2" | État
! colspan="2" | Symbole
|-
! 0 !! width="50%" | 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 <span style="color:blue">'''STOP'''</span>
|
* É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 : {{nobr|... 0 0 1 0 1 1 1 1 1 1 1 1 {{Souligner|1}} 1 1 1 0 0 ...}}

=== 5 états ===
Pour 5 états, le castor affairé est la machine suivante<ref name="michel" />{{,}}<ref name="heiner_52" /> :

{| class="wikitable"
|-
! rowspan="2" | État
! colspan="2" | Symbole
|-
! 0 !! width="50%" | 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 <span style="color:blue">'''STOP'''</span>
|
* Écrire le symbole '''0'''
* Déplacer le ruban à '''droite'''
* Passer à l'état '''A'''
|}

Cette machine produit {{formatnum:4098}} symboles '''1''' en {{formatnum:47176870}} pas. Les symboles '''1''' ne sont pas consécutifs : {{formatnum:8191}} symboles '''0''' sont intercalés.

Découverte en 1989, cette machine n'a été démontrée maximale qu'en 2024<ref>{{lien web |langue=en |titre=[july 2nd 2024] we have proved "bb(5) = 47,176,870" |url=https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 |site=The Busy Beaver Challenge |date=02-07-2024 |consulté le=08-07-2024}}.</ref>.

=== 6 états ===
À 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<ref>{{Lien web |langue=anglais |auteur=Sligocki |titre=BB(6, 2) > 10↑↑15 |url=https://www.sligocki.com/2022/06/21/bb-6-2-t15.html |date=2022}}</ref> :

{| class="wikitable"
|-
! rowspan="2" | État
! colspan="2" | Symbole
|-
! 0 !! width="50%" | 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 <span style="color:blue">'''STOP'''</span>
|-
! 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 <math>10 \uparrow \uparrow 15</math> étapes où <math>\uparrow</math> est la [[notation des flèches de Knuth]].
Autrement dit, le nombre d'étapes qu'elle effectue avant de s'arrêter est <math>10^{10^{10^{.^{.^{.^{10}}}}}}</math> avec 15 itérations de puissance de 10.

Le précédent record était de {{nombre|7,412e36534}} étapes<ref>{{Lien web |langue=anglais |auteur=Heiner Marxen |titre=6-state 2-symbol #b (Pavel Kropitz) |url=http://turbotm.de/~heiner/BB/simKro62_b.html |date=2010}}</ref>.
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 {{nombre|7,412e36534}} en base décimale est {{nombre|36535}}, tandis que celui nécessaire pour écrire <math>10 \uparrow \uparrow 15</math> est <math>(10 \uparrow \uparrow 14) + 1</math> ; or, rien que <math>10 \uparrow \uparrow 3</math> vaut déjà <math>10^{10^{10}}</math>= <math>10^{10\,000\,000\,000}</math>.

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<ref>{{Article|langue=anglais|auteur1=Scott Aaronson|titre=The Busy Beaver Frontier|périodique=article|date=2020|lire en ligne=https://www.scottaaronson.com/papers/bb.pdf|format=pdf|pages=15}}</ref>.

== Valeurs connues ==
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 [[Borne inférieure|bornes inférieures]].

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

:<math>\Sigma(2k) > 3 \uparrow^{k-2} 3 > A(k-2,k-2)</math>

où <math>\uparrow</math> est la [[notation des flèches de Knuth]] et ''A'' est la [[fonction d'Ackermann]]<ref name="green" />.

Ainsi :

:<math>\Sigma(10) > 3 \uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow 3^{3^3} = 3^{3^{3^{.^{.^{.^3}}}}}</math>

(où le dernier terme est une tour de 3<sup>27</sup> = {{formatnum:7625597484987}} exposants), et :

:<math>\Sigma(12) > 3 \uparrow\uparrow\uparrow\uparrow 3 = g_1</math>

où g<sub>1</sub> 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<ref name="heiner" />{{,}}<ref name="michel" />. 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''.

{| class="wikitable" style="text-align: right"
|+ ''S''(''n'',''m'')
|-
!
! 2 états
! 3 états
! 4 états
! 5 états
! 6 états
|-
! 2 symboles
| 6
| 21
| 107
| {{nombre|47176870}}
| ≥ <math>10 \uparrow \uparrow 15</math>
|-
! 3 symboles
| 38
| ≥ {{nombre|119112334170342540}}
| ≥ {{nombre|1,0e14072}}
| ?
| ?
|-
! 4 symboles
| ≥ {{nombre|3932964}}
| ≥ {{nombre|5,2e13036}}
| ?
| ?
| ?
|-
! 5 symboles
| ≥ {{nombre|1,9e704}}
| ?
| ?
| ?
| ?
|-
! 6 symboles
| ≥ {{nombre|2,4e9866}}
| ?
| ?
| ?
| ?
|}

{| class="wikitable"
|+ Σ(''n'',''m'')
!
! 2 états
! 3 états
! 4 états
! 5 états
! 6 états
|-
! 2 symboles
| 4
| 6
| 13
| ≥ {{nombre|4098}}
| ?
|-
! 3 symboles
| 9
| ≥ {{nombre|374676383}}
| ≥ {{nombre|1,3e7036}}
| ?
| ?
|-
! 4 symboles
| ≥ {{nombre|2050}}
| ≥ {{nombre|3,7e6518}}
| ?
| ?
| ?
|-
! 5 symboles
| ≥ {{nombre|1,7e352}}
| ?
| ?
| ?
| ?
|-
! 6 symboles
| ≥ {{nombre|1,9e4933}}
| ?
| ?
| ?
| ?
|}

== Références ==
<references>
<ref name="radó">{{Article
 | langue       = en
 | prénom1      = Tibor
 | nom1         = Radó
 | lien auteur1 = Tibor Radó
 | titre        = On Non-Computable Functions
 | périodique   = Bell Systems Technology Journal
 | volume       = 41
 | numéro       = 3
 | mois         = mai
 | année        = 1962
 | pages        = 877-884
 | url texte    = http://www.alcatel-lucent.com/bstj/vol41-1962/articles/bstj41-3-877.pdf
}}</ref>
<ref name="oeis">{{OEIS|id=A028444}}</ref>
<ref name="heiner">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/
 | titre  = Busy Beaver
 | auteur = Marxen Heiner
 | date   = 7 novembre 2011
}}</ref>
<ref name="heiner_22">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/simTM22_bb.html
 | titre  = 2-state Busy Beaver (by T.Rado)
 | auteur = Heiner Marxen
 | date   = 6 juillet 2010
}}</ref>
<ref name="heiner_23">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/simTM23_cb.html
 | titre  = 2-state 3-symbol currently best (by Brady / Michel)
 | auteur = Heiner Marxen
 | date   = 6 juillet 2010
}}</ref>
<ref name="heiner_32_sigma">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/simTM32_bbO.html
 | titre  = 3-state Busy Beaver (most ones) (by T.Rado)
 | auteur = Heiner Marxen
 | date   = 6 juillet 2010
}}</ref>
<ref name="heiner_32_s">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/simTM32_bbS.html
 | titre  = 3-state Busy Beaver (most steps) (by T.Rado)
 | auteur = Heiner Marxen
 | date   = 6 juillet 2010
}}</ref>
<ref name="heiner_42">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/simTM42_bb.html
 | titre  = 4-state Busy Beaver (by A.Brady)
 | auteur = Heiner Marxen
 | date   = 6 juillet 2010
}}</ref>
<ref name="heiner_52">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/simmbL5_1.html
 | titre  = 5-state TM #1 from MaBu-List
 | auteur = Heiner Marxen
 | date   = 6 juillet 2010
}}</ref>
<ref name="heiner_33">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/simLig33_b.html
 | titre  = 3-state 3-symbol #b (T.J. & S. Ligocki)
 | auteur = Heiner Marxen
 | date   = 6 juillet 2010
}}</ref>
<ref name="michel">{{en}} {{Lien web
 | url    = http://www.logique.jussieu.fr/~michel/ha.html
 | titre  = Historical survey of Busy Beavers
 | auteur = Pascal Michel
 | date   = juin 2012
}}</ref>
<ref name="green">{{Article
 | langue       = en
 | prénom1      = Milton W.
 | nom1         = Green
 | titre        = A Lower Bound on Rado's Sigma Function for Binary Turing Machines
 | périodique   = 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design
 | année        = 1964
 | pages        = 91-94
 | doi          = 10.1109/SWCT.1964.3
}}</ref>
<!-- Référence plus utilisée depuis le 13 mars 2023 (202256553).
<ref name="heiner_62">{{en}} {{Lien web
 | url    = http://turbotm.de/~heiner/BB/simKro62_b.html
 | titre  = 6-state 2-symbol #b (Pavel Kropitz)
 | auteur = Heiner Marxen
 | date   = 6 juillet 2010
}}</ref>
-- Référence plus utilisée depuis le 3 juillet 2024 (216476895).
<ref name="skelet">{{en}} {{Lien web
 | url    = http://skelet.ludost.net/bb/nreg.html
 | titre  = Busy Beaver nonregular machines for class TM(5)
 | auteur = Georgi Georgiev (Skelet)
 | date   = 16 mai 2003
}}</ref>
-->
</references>

== Voir aussi ==
{{Autres projets
 | commons = Category:Busy beavers
 | commons titre = Castors affairés
}}

=== Bibliographie===
* Lin, Shen and Radó, Tibor (1965), [http://portal.acm.org/citation.cfm?doid=321264.321270 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 <math>\Sigma(3) = 6</math> 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, {{numéro|162}} (avril 1983), {{p.|647-665}}. Une preuve de <math>\Sigma(4)</math> = 13

=== Articles connexes ===
* [[Machine de Turing]]
* [[Complexité de Kolmogorov]]
* [[Turmite]]

=== Liens externes ===
* {{en}} [http://mathworld.wolfram.com/BusyBeaver.html Busy Beaver] ([[MathWorld]])
* {{en}} [http://turbotm.de/~heiner/BB/ Busy Beaver - Currently Known Results] (Heiner Marxen)
* {{en}} [http://www.logique.jussieu.fr/~michel/ha.html Historical survey of Busy Beavers] (Pascal Michel)

{{Portail|informatique|logique|mathématiques|jeux}}

[[Catégorie:Calculabilité]]
[[Catégorie:Grand nombre]]