Ma page "Castor Actifs"

Un projet en cours : BBfind-BBstats.

Je recherche des castors actifs ("Busy Beavers" en anglais). Plus généralement, je cherche à établir une taxonomie des machines de Turing à petit nombre d'états.

Historiquement, la question a soulevée par T. Rado :

Avant de discuter de ce problème précis et de refléchir aux moyens algorithmiques de répondre à cette question, une petite introduction s'mpose.

Une machine de Turing à n états est un ruban doublement infini sur lequel on peut écrire et les des caractères d'un alphabet A, associé à une fonction de transfert phi définie sur [[1,n]]xA, à valeurs dans Ax{G,D}x{[[1,n]]UH}. Quand la machine se trouve dans l'état i compris entre 1 et n, et qu'elle lit le caractere c sur le ruban, elle "exécute" l'instruction phi(i)=(c',M,e') en écrivant le caractère c' sur le ruban, en déplaçant le curseur selon le mouvement M (Gauche ou Droite), et en se mettant dans le nouvel état e'. Si ce nouvel état est l'état spécial H, la machine s'arrète.

La règle du jeu du problème de l'arrêt consiste à démarrer une machine de Turing dans l'état initial 1, sur un ruban initialement composé de 0 (ou de blancs). Il s'agit de savoir si l'on peut construire un algorithme (en gros, une machine de Turing TH) recevant la définition d'une machine de Turing quelconque T, qui puisse décider si cette machine s'arrète en un temps fini. Bien entendu, ceci exclut la stratégie meule de foin consistant à faire exécuter par la machine TH le programme de T, et à renvoyer vrai si TH s'arrête et faux sinon, puisque cette "méthode" ne donne la réponse en un temps fini que si T s'arrête effectivemet. Or il extrèmement simple de construire des machines arbitrairement complexes qui ne s'arrète pas (par exemple la machine à un seul état, qui quand elle lit un zéro écrit un un, se déplace à gauche et reste dans l'état 1, remplit indéfiniment la partie gauche du ruban de uns ; remarquons à cette occasion qu'une définition partielle de la fonction de transfert suffit parfois à "faire fonctionner" le programme).

Turing et Post ont démontré qu'une telle machine n'existe pas, et donc que le problème de l'arrêt est indécidable. Ce résultat en rejoint d'autres dans le domaine de la formalisation des mathématiques, et nous retrouverons des techniques de démonstration issues de ce monde par la suite.

Si l'on choisit de ne travailler qu'avec des machines à n états, n étant fixé à l'avance, on peut s'imaginer que le problème se simplifie. Pour savoir si une machine donnée s'arrête, il suffit de la lancer, et de l'arrêter dès qu'elle a effectué plus d'"instructions" que toute autre machine  à n états. Il ne doit pas être bien compliqué de parler de la fonction S qui à n associe le plus grand nombre de pas que peut exécuter une machine à n états sans boucler indéfiniment. Mais dès qu'on essaye de mettre en forme le calcul de cette fonction, on recontre tout un tas de nombres astronomiques (et c'est un DOUX euphémisme, comme nous allons le voir) et de difficultés insurmontables. Ce qui, en y repensant, n'est pas étonnant : la connaissance d'une telle fonction S entrainerait automatiquement l'existence d'un algorithme de décision du problème de l'arrêt.

Qu'est-ce que cela veut dire concernant la fonction S ? Tout simplement que cette fonction n'est pas calculable (sous-entendu "par une machine de Turing). Or, il a été démontré qu'une telle machine, aussi simple semble-t-elle être, est suffisamment puissante pour effectuer tout travail actuellement acomplissable par un ordinateur. Ceci implique en particulier que pour toute fonction f de source IN*, il existe un rang N₀ tel que pour n>N₀,f(n)<S(n). Autrement dit, S majore toute fonction calculable, et en particulier toute fonction humainement imaginable.

"Mais pourquoi ne pas faire une exploration exhaustive pour les premières valeurs de n", me direz-vous ? "Les ordinateurs sont suffisamment puissants aujourd'hui pour explorer des milliards de possibilités à chaque seconde ? Or il est bien connu que milliard est un seuil magique à partir duquel apparaissent des comportements bien au delà de nos modestes facultés." Certes. Mais un rapide calcul va vous montrer que ces milliards d'instructions ne valent pas un pet de musariagne par rapport à la formidable complexité du problème. Pour définir une transition dans une machine à n états, on a besoin de donner un caractère à écrire parmi 0 et 1, une direction parmi G et D, et un nouvel état parmi les entiers entre 1 et n, plus l'état particulier H. Ainsi, il y a 4n+4 transitions possibles. Comme une machine de Turing à état nécessite la définition de 2n transitions, il y a N(n) = (4n+4)2n machines de Turing à n états différentes. On verra que cette fonction grandit monstrueusement trop vite pour nos pauvres stations bourrées de giga-Hertz.

Parlons maintenant de cette fameuse fonction sigma, qui donne le nombre maximum de uns qu'une machine de Turing à n états peut écrire sur un ruban initialement vide tout en s'arrètant. Il n'est pas tout à fait aussi simple de le prouver, mais T. Rado a démontré que cette fonction n'est pas non plus calculable. Ceci fournit d'ailleurs une autre preuve du fait que S n'est pas calculable. Nous pouvons bien parler de cette quantité sigma(n) pour n'importe quel entier n puisque le nombre de machine a n états est fini, et le nombre de machine s'arrètant lui est inférieur.

Pour résumer tout ceci, un petit tableau nous aidera à faire le point :

On constate tout de suite que le nombre N(n) dépasse largement le cap du milliard pour n = 4 seulement ! Il semble déjà illusoire d'espérer faire tourner toutes les machines à 4 ou 5 états, même en "trichant" : en arrêtant toutes les machines à 4 états après 107 pas, cela prendrait déjà trois quarts d'heures à un ordinateur simulant une étape élémentaire toutes les nano-secondes (ce qui semble TRES optimiste !), et si on tentait l'expérience avec des machines à 5 états, il faudrait au bas mot 95 000 ans. Si une chose est certainement décidable, c'est la certitude qu'aucun ordinateur ne pourra jamais rester en état de fonctionnement aussi longtemps, ne serait-ce que parce que l'Homme aura trouvé entre temps 17345 raisons et manières différentes de faire exploser sa planète (et sans bouger les oreilles, bien-sûr), ce qui mettra automatiquement fin à l'expérience. Quelques ingénieurs cosmiques ont mis en oeuvre de tels ordinateurs sur une échelle de temps réellement astronomique, mais les résultats à long termes sont certainement décevants, et ce mode de calcul a été abandonné depuis (la planète Terre était un exemple d'un tel "super-ordinateur", mais les Vogons, qui n'y ont rien compris, l'ont rasée, comme chacun sait).

La suite (sigma(n))_n, puisqu'il faut bien s'intéresser un peu à elle, a un départ tout à fait anodin. Toute personne ayant déjà rencontré des suites dans sa vie ne peut qu'être déçu par un tel départ. Sur un 100m (4 états), sigma est largement battue par les suites arithmétiques. Sur un 200m, (5 états), une suite géométrique convient sans problème. Mais si on regarde du coté du tour de piste (6 états), on commence à avoir un peu le vertige. Ainsi, si je me souviens bien de mes cours de physique et de mes lectures ésotériques, il y aurait de l'ordre de 10¹⁰⁰ particules élémentaires dans l'univers. Une machine de Turing à 6 états peut donc potentiellement énumérer chaque particule de notre univers plus de huit fois. Sacré bestiole, quand on y pense. Remarquons aussi qu'elle met pour ce faire un temps qui n'est lui plus du tout astronomique (ou alors adressez-vous aux frères Bogdanov, moi j'abandonne) : notre univers aurait de l'ordre de 15 milliards d'années (qu'Hubert Reeves me pardonne si j'en oublie une petite dizaine en route, c'est le nombre de zéros qui nous intéresse), soit un demi milliard de milliards de secondes (il parait qu'on est à peu près à la moitié de la vie de l'univers... quelle coïncidence !). Une machine de Turing exécutant 2 milliards d'instructions par seconde aurait donc exécuté depuis le début de l'existence de l'univers (le premier jour, Dieu créa la machine de Turing et lui dit : "grouille toi, on n'a pas toute la vie") de l'ordre de 10²⁷ instructions. Comparez à 10¹⁷³⁰, respirez un grand coup, recommencez à essayer d'intégrer ce nombre dans votre esprit, puis faites comme tout le monde : abandonnez. A quoi bon ?

Pour réver un peu, essayer d'imaginer le nombre de chiffres du nombre de chiffre de sigma(7) ou S(7). Et si vous en voulez encore, allez vous faire soigner sur le site de Robert Munafo consacré aux grands entiers (mais VRAIMENT GRANDS, hein ?), en particulier ici où l'on parle d'une autre machine extraordinaire de Heiner Marxen.

 Si vous vous intéressez à ce sujet, ne manquez pas de visiter la page de ce dernier Heiner Marxen, pour découvrir en particulier les "trucs" qui lui ont permis de trouver ces bornes inférieures (car on ne sait toujours pas les valeurs de sigma(5) et S(5), même si on commence à avoir une petite idée). Elle contient un certain nombre de documents sur le sujet, dont "Attacking the BB(5)" dont je me suis largement inspiré pour ce programme, des sources Awk pour expérimenter sur le sujet, et des liens vers d'autres documents, dont ce document donnant la démonstration de la non calculabilité de sigma.

D'autres pages traitent de problèmes similaires : un groupe du Rensselaer Polytechnic Institute s'attaque au problème avec des machines aux règles plus simples,  où l'on ne peut choisir à chaque étape qu'entre une écriture sur le ruban et un déplacement (mais pas les deux).

Quant-à Rick J. Griffiths, il étudie le problème avec des machines à registres. Les techniques diffèrent, mais de nombreux points suivent des logiques similaires. En particulier la fonction sigma pour de telle machines a l'air d'avoir un départ beaucoup plus tranquille. Mais comme elle n'est elle non plus pas calculable, et que le champ d'exploration est tout aussi vaste, de nombreux challenges restent ouverts.

J'ai écrit un programme qui aborde la question, en Objective Caml : castor_laborieux-0.3.

D'autres versions plus anciennes de mon projet : la version 0.1, basique, et version 0.2 sans backtracking.

La prochaine version sera entièrement revue, il y aura des lamas en couleur, déguisés en castor et dansant des danses traditionnelles tchèques, ça c'est sûr, et peut-être, mais il ne faut pas trop réver, une documentation plus complète sur ce sujet passionnant.