Journal d'un terrien

Web log de Serge Boisse

On line depuis 1992 !

Recherche personnalisée

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 n0 au delà duquel
sigma(n) > f(n) pour n > n0

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 :

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

Journal d'un terrien

Commentaires (2) :

Page : [1] 

Serge Boisse
Le 03/06/2011 à 19h23
Pour Fabien :

Oui, la fonction de Rado croît aussi plus vite que la suite de Goodstein !
Fabien
Le 03/12/2008 à 00h15
Bonjour , donc si j'ai bien lu votre article , la fonction de rado croit plus vite que factorielle ,exp , ackermann... . Mais croit elle plus vite que les suites de goodstein ?



merci


Ajouter un commentaire (pas besoin de s'enregistrer)

Pseudo :
Message :


image de protection
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !
Ah oui : le html genre <br>, <a href=...>, <b>b etc. ne fonctionne pas dans les commentaires. C'est voulu.
< Retour en haut de la page