Busy beaver

Le castor affairé, dont le nom a été proposé par le mathématicien hongrois Tibor Radó, est l'un des premiers exemples de fonction non calculable. Un castor affairé est une machine de Turing à n états qui écrit un maximum de "1" sur son ruban avant de s'arrêter. Déterminer le « castor affairé » pour un nombre n donné est un problème insoluble algorithmiquement ; en pratique on ne peut même pas espérer le résoudre pour un nombre n au-delà de 10. Ce problème abstrait a été, dès son origine, illustré par un jeu.

Sommaire 1 Le jeu du castor affairé 1.1 Exemple, pour n=2 1.2 Exemple, pour n=6 2 Le problème du castor affairé 2.1 Fonction du castor affairé 2.2 Preuve de l'incalculabilité de Σ(n)[2]. 3 Références

Le jeu du castor affairé

Imaginons un jeu, que nous appelons le « castor affairé ». Dans ce jeu, il y a trois objets:

• Un ruban "infini" constitué d'une infinité de cases
• Une machine qui peut écrire soit 0 soit 1 sur chaque case du ruban
• Une liste de n instructions déterminant le comportement de cette machine

Le but du jeu est de trouver l'ensemble des règles qui permet d'écrire le plus de 1 possible sur la bande avant de s'arrêter, en suivant les règles suivantes:

Règle #1: La machine possède un nombre fini d'états (dont un état spécial STOP). Un état est défini par:

• son instruction dans la liste d'instructions fournies (appelons les 1, 2, 3... n) ;
• le symbole (0 ou 1) dans la case courante.

L'état suivant est déterminé par l'état courant de manière unique. Plus précisément, un état donne à la machine une liste d'actions à faire pour aller à l'état suivant (l'ordre est important) à savoir:

• Une action d'écriture sur la bande infinie. La machine peut écrire un 0, ou un 1.
• Une action de déplacement de la bande infinie (vers la gauche ou vers la droite).
• Un arrêt (transition vers l'état STOP)

Règle #2: La liste d'instructions ne peut pas changer au cours du jeu.

Règle #3: Le jeu commence à l'instruction 1 avec la bande remplie de 0.

Règle #4: Le jeu finit tôt ou tard sur l'état STOP (après tout, il est facile de faire un ensemble d'instructions qui ne fait qu'écrire une infinité de 1).

Avec ces règles, la machine est une machine de Turing à deux symboles.

Exemple, pour n=2

Essayons avec l'ensemble d'instructions suivant:

Instruction \ Nombre dans la case courante	1	2
0	Écrire 1 Déplacer le ruban vers la droite Passer à l'instruction 2	Écrire 1 Déplacer le ruban vers la gauche Passer à l'instruction 1
1	Écrire 1 Déplacer le ruban vers la gauche Passer à l'instruction 2	Écrire 1 Passer à l'état STOP

Nous commençons initialement à l'instruction 1, et le ruban est rempli de 0 (représentés ici par une case vide)

				Case lue						Instruction:
										1

La machine écrit donc 1, déplace le ruban vers la droite et passe à l'instruction 2

				Case lue						Instruction:
										1
					1					2

Toujours avec ces instructions, la machine écrit donc 1, déplace le ruban vers la gauche et passe à l'instruction 1

				Case lue						Instruction:
										1
					1					2
			1	1						1

Et ainsi de suite, jusqu'à arriver à la situation suivante

				Case lue						Instruction:
										1
					1					2
			1	1						1
		1	1							2
	1	1	1							1
		1	1	1	1					2

À ce moment là, comme indiqué dans les instructions, la machine s'arrête après avoir écrit quatre 1. C'est le mieux qu'on puisse faire avec deux symboles et deux instructions.

Exemple, pour n=6

	1	2	3	4	5	6
0	Écrire 1 Déplacer le ruban vers la droite Passer à l'instruction 2	Écrire 0 Déplacer le ruban vers la droite Passer à l'instruction 3	Écrire 1 Déplacer le ruban vers la gauche Passer à l'instruction 4	Écrire 0 Déplacer le ruban vers la gauche Passer à l'instruction 5	Écrire 0 Déplacer le ruban vers la droite Passer à l'instruction 1	Écrire 1 Déplacer le ruban vers la gauche Passer à l'instruction 1
1	Écrire 0 Déplacer le ruban vers la gauche Passer à l'instruction 6	Écrire 0 Déplacer le ruban vers la droite Passer à l'instruction 4	Écrire 1 Déplacer le ruban vers la droite Passer à l'instruction 5	Écrire 0 Déplacer le ruban vers la gauche Passer à l'instruction 4	Écrire 1 Déplacer le ruban vers la droite Passer à l'instruction 3	Écrire 1 Passer à l'état STOP

Ce jeu d'instructions permet d'écrire environ 1,2 x 10⁸⁶⁵ occurrences du symbole 1 en 3 x 10¹⁷³⁰ étapes. Voir la page de Heiner Marxen pour plus de machines à 6 instructions et les valeurs exactes.

Le problème du castor affairé

Maintenant que vous êtes devenu un très bon joueur, nous vous proposons de prendre la place de l'arbitre. Des joueurs vont vous soumettre leur liste d'instructions, et vous aimeriez déterminer:

• Quels sont les joueurs éliminés car ne respectant pas la quatrième règle (la machine doit s'arrêter un jour)
• Quel est le meilleur joueur, quel est le score de chaque joueur
• Le meilleur joueur peut il recevoir le titre de "castor affairé" ? (c'est-à-dire qu'il a trouvé la liste d'instructions qui donne le meilleur score)

Ceci est un défi à la calculabilité. On peut démontrer que dans le cas général, on ne peut pas répondre algorithmiquement à la troisième question, car la fonction qui prend comme donnée une machine et répond si elle est ou n'est pas un castor affairé ne peut pas être décrite par un algorithme (par une machine de Turing par exemple). Comme conséquence, on peut affirmer que mêmes les ordinateurs les plus puissants ne pourront jamais décerner le titre de castor affairé à une machine. D'ailleurs dès la valeur 10 (et probablement même bien avant !) et même en utilisant des astuces et des procédés ad hoc c'est sans espoir.

Fonction du castor affairé

Ce qui suit est l'approche formelle du problème.

On voit qu'il n'existe qu'un nombre fini de machines de Turing à n états et 2 symboles. De plus, il est facile de démontrer que certaines s'arrêtent (tout simplement une machine qui écrit 1 puis s'arrête immédiatement après la première action). Maintenant, définissons:

• E_n l'ensemble fini et non vide des machines de Turing à n états et 2 symboles qui finissent par s'arrêter ;
• σ(M) (M étant un élément de E_n) comme le nombre de 1 écrits par la machine M avant de s'arrêter ;
• Σ(n) comme étant le maximum de σ sur E_n. C'est la fonction du castor affairé.

Σ(n) est totale et monotone. Elle est totale, car elle est manifestement définie pour tout n ≥ 1, et elle est monotone car on a la certitude que Σ(n) < Σ(n + 1) (si on augmente le nombre d'états permis, cela induit forcément que l'on peut produire plus de 1).

Radó a prouvé que dans le cas général, Σ(n) n'est pas calculable. Toutefois, sa valeur est connue pour certains cas particuliers (le plus évident étant Σ(1) = 1, et on peut montrer que Σ(2) = 4, Σ(3) = 6 et Σ(4) = 13 ^[1]), et dans d'autres cas la valeur est minorée (il suffit de trouver un exemple pour lequel la machine s'arrête, le nombre de 1 écrits étant donc un minorant).

Preuve de l'incalculabilité de Σ(n)^[2].

Il existe plusieurs moyens de prouver l'incalculabilité de Σ(n), l'un d'entre eux est d'utiliser la fonction de combinaison des machines de Turing.

Hypothèse de départ: Supposons que Σ(n) est calculable.

Si Σ(n) est calculable alors la fonction D(n) = Σ(2n), l'est également. Si la fonction D(n) est calculable, alors peut-être représentée à l'aide d'une machine de Turing, que nous appellerons M_d, et qui possédera un nombre fini d'état k (que nous ne connaissons pas).

Prenons maintenant la fonction u(f(n)) = f(n), qui se contentera d'afficher la valeur de retour d'une certaine fonction passée en paramètre. À l'instar de la fonction D, cette fonction u peut-être représentée par une machine de Turing, que nous appellerons M_u. On prendra note qu'il est possible de coder cette machine M_u en utilisant n états (nous pourrions l'implémenter en moins que cela, mais cela ne nous intéresse pas dans le cadre de cette preuve).

Définissons maintenant la machine M, qui est une composition des machines M_u et M_d. Autrement dit, nous allons passer en paramètre de la fonction u la fonction D afin de réaliser l'opération u(D(n)). Du fait de la composition, cette machine M sera composée de n + k états et, conformément aux descriptions précédentes, écrira sur une bande vierge D(n) = Σ(2n) symboles 1.

En résumé, nous avons obtenu une machine de Turing de n + k états et qui produit Σ(2n) symboles. Que pouvons-nous dire sur la valeur de Σ(n + k), qui est le nombre de 1 pouvant être écrits avec n + k états ? Eh bien nous pouvons affirmer que cette fonction retournera une valeur plus grande ou en tout cas égale au nombre de 1 écrits par la machine M, c'est à dire: Σ(n + k) ≥ Σ(2n)^[3].

Selon l'aspect monotone de Σ(n), on peut affirmer la chose suivante: pour tout k < n, Σ(2n) > Σ(n + k). Cette inéquation, combinée avec celle obtenue précédemment, nous donne: Σ(2n) > Σ(n + k) ≥ Σ(2n) | n < k.

Cette évidente contradiction nous permet d'affirmer que notre hypothèse de départ était fausse, Σ(n) n'est pas calculable.

Références

• Radó, Tibor (1962), On non-computable functions, Bell Systems Tech. J. 41, 3 (mai 1962). C'est ici que Radó a donné la preuve de la non calculabilité de Σ(n)
• Lin, Shen and Radó, Tibor (1965), Computer Studies of Turing Machine Problems, Journal of the Association for Computing Machinery, Vol. 12, No. 2 (Avril 1965), pp. 196-212. Ceci inclut la thèse de Lin, qui a montré que Σ(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-state Turing machines, Mathematics of Computation, Vol. 40, No. 162 (Avril 1983), pp. 647-665. Une preuve de Σ(4) = 13

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