math

Busy Beaver

Pour coder en FORTRAN, j’ai décidé de retrouver les Busy Beavers de petite taille (nombre d’états  n \leqslant 4 ).

Comme les valeurs de  S(n,2) sont connues pour  n petit, j’ai simplement simulé toutes les Machines de Turing (TM) à  n état(s) et deux symboles pendant 125 steps (soit  S(4,2)+18 steps). Celles qui ne se sont pas arrêtées après  S(n,2) steps ne s’arrêtent jamais. Et Ô bonheur, j’ai retrouvé les bonnes valeurs :

n  S(n,2)  \Sigma(n,2)
1 1 1
2 6 4
3 21 6
4 107 13

Mais la partie interessante de ce projet, pour moi, c’est les temps qu’il a fallu à mon pauvre ordinateur pour calculer tout ça. Pour n=1, mon ordinateur teste toutes les TM possibles en quelques fractions de secondes. Mais pour n=4, il lui a fallu 12 (!) jours. Les TM avec plus d’états ne sont pas (beaucoup) plus difficiles à simuler, mais il y en a beaucoup plus :

 TM(n) = (4n+4)^{2n}

Avec  TM(n) le nombre de TM à n états et deux lettres. Pour chacune des  2n combinaisons de [état(n) + lecture(2)], il y a  2\times2\times(n+1) choix de [direction(2) + écriture(2) + état(n+1)]. Inutile de dire que  TM(n) grandit vite.

Voici un tableau qui récapitule le nombre de TS à tester pour chaque nombre d’état et le temps qu’il a fallu pour calculer tout ça :

n  TM(n) Temps (s)
1 64 0.007
2 20736 0.66
3 1.7×107 537 (9 min)
4 2.6×1010 1036800 (288 h)

J’ai tracé le temps de calcul en fonction du nombre de TM à tester, en log-log.

BBgraph1

Ça à l’air suspicieusement linéaire, mais avec si peu de points, je ne m’avancerai pas. Juste pour être sûr, j’ai aussi tracé le ratio  \frac{\text{Temps de calcul}}{TM(n)}  en fonction de  TM(n) :

BBgraph2

C’est moche.

Je suis déçu de ne pas avoir plus de points, mais pour  n=5 , non seulement il faudra tester  63403380965376=6.3\times10^{13} machines, mais je ne saurais pas quand les arréter, puisque  S(5,2) n’est pas connu. Je soupçonne fortement que le temps de calcul passerait de toutes façons de interminable à stupidement long.

Publicités
Par défaut

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s