Castor affairé - Définition

Introduction

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.

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 (il est donc interdit 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 n°1	Instruction n°2
Case lue : 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
Case lue : 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)

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

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

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

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