Le castor affaire

Le castor affairé

Un "castor affairé", c'est la machine de Turing à n états qui écrit un maximum de "1" sur le ruban avant de s'arrêter. Déterminer quel est le castor affairé pour un nombre détat n est un problème indécidable (du fait que le pb de l'arrêt d'une machine de Turing est indécidable).

Ou bien, de manière équivalente, définissons la fonction de Rado (inventée par Tibor Rado) par :

sigma(n) = nombre maxi de "1"  qu'une machine de Turing à n état peut écrire avant de s'arrêter.

Sigma(n) est une fonction non calculable.

C'est la fonction définissable en termes de machines de Turing (ou tout simplement "humainement définissable" si l'on adopte la thèse de Church-Turing) qui croît le plus rapidement : la fonction sigma croît plus vite que tout fonction calculable (factorielle, exponentielles ou puissances empilées, fonction d'ackermann, etc).

C'est à dire que quelle que soit la fonction f:N->N calculable qui vous pourrez inventer, il existera un n₀ au delà duquel
sigma(n) > f(n) pour n > n₀

Il n'empêche que pour de petites valeur de n, on peut tester exhaustivement toutes les machines de Turing à n état et que des "fous" ont déjà fait l'exercice jusqu'à 6 états avec les résultats suivants :

castor a 1 état : sigma = 1
etat   0 lu   1 lu
1   1,stop   1,stop
castor a 2 etats : sigma = 4
etat   0 lu   1 lu
1   1,d,e2   1,g,e1
2   1,g,e1   1,stop
castor a 3 etats : sigma = 5, 13 transitions
état   0 lu   1 lu
1   1,d,e2   1,g,e3
2   1,g,e1   1,d,e2
3   1,g,e2   1,stop
castor a 5 etats : sigma = 501 
état   0 lu   1 lu
1   1,d,e2   0,g,e3
2   1,d,e3   1,d,e4
3   1,g,e1   0,d,e2
4   0,d,e5   1,stop
5   1,g,e3   1,d,e1
super castor a cinq etats : sigma = 1915 : ne semble pas marcher ?
etat   0 lu   1 lu
1   1,d,e2   1,g,e3
2   0,g,e1   0,g,e4
3   1,g,e1   1,stop
4   1,g,e2   1,d,e5
5   0,d,e4   0,d,e2
BB(5) >= 4098 was found by Heiner Marxen and Juergen Buntrock
in September 1989. The number of shifts SH is 47,176,870. The
instructions read:
1B -> 21L, 11 -> 31R, 2B -> 31L, 21 -> 21L, 3B -> 41L,
31 -> 5BR, 4B -> 11R, 41 -> 41R, 5B -> S1L, 51 -> 1BR.
This solution has been published in:
H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.
Bulletin of the EATCS, 40, pages 247-251, February 1990.

Pour 6 états, on a trouvé de bons "candidats", mais on n'est pas sùr d'avoir trouvé le Castor à 6 états :
Marxen and Buntrock also present a six-state beaver:
BB(6)>=136,612 and SH>=13,122,572,797.
1B -> 21L, 11 -> 11L, 2B -> 31R, 21 -> 21R, 3B -> 6BR,
31 -> 41R, 4B -> 11L, 41 -> 5BR, 5B -> 1BL, 51 -> 31R,
6B -> 51L, 61 -> S1L.
This is not the current record for n = 6.  The current record is
95,524,079 marks in
8,690,333,381,690,952 steps :
(dur dur pour vérifier !)
auteur : Heiner Marxen, extrait de beaver.ps cité ci dessous.
etat   0 lu   1 lu
1   1,d,e1   1,d,e2
2   1,g,e3   1,g,e2
3   0,d,e6   1,g,e4
4   1,g,e1   1,g,e5
5   1,g,stop  1,g,e6
6   0,g,e1   1,g,e3
J'utilise la fonction sigma dans ma théorie cosmologique.
En outre je propose une machine de Turing révolutionnaire dont la rapidité croît avec le temps.

---

liens divers sur le web concernant les MdT et les castors affairés :

• castors
• Busy Beaver Turing Machine

> La suite : Une machine de turing à accélération