Auteur: Serge Boisse
Date: Le 18/07/2024 à 18:03
Type: web/MOC
tags: 
pub: oui
commentaires: ouiCopier

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) 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; 6 transitions
etat     0 lu      1 lu  
1        1,d,e2    1,g,e1  
2        1,g,e1    1,stop  
  
castor à 3 etats : sigma = 6, 14 transitions  
état     0 lu      1 lu  
1        1,d,e2    1,d,STOP 
2        0,d,e3    1,d,e2  
3        1,g,e3    1,g,e1  

castor à 4 états : sigma = 13; 107 pas 
   (les "1" ne sont pas consécutifs)
état     0 lu      1 lu  
1        1,d,e2    1,g,e2  
2        1,g,e1    1,g,e3  
3        1,d,STOP  1,g,e4  
4        1,d,e4    0,d,e1  

castor a 5 etats : sigma = 4098, 47176870 pas  
état     0 lu      1 lu  
1        1,d,e2    0,d,e3  
2        1,g,e3    1,g,e2  
3        1,g,e4    0,d,e5  
4        1,d,e1    1,d,e4  
5        1,g,STOP  0,d,e1  
Copier

BB(5) >= 4098 a été prouvé par Heiner Marxen and Juergen Buntrock
en September 1989.
Cette solution a été publiée dans:

H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.
Bulletin of the EATCS, 40, pages 247-251, February 1990.

Mais ce n'est qu'en 2024 qu'il a été prouvé par une équipe dirigée par Tristan Stérin, à l'aide du prouveur de théorèmes COQ, que cette machine est bien maximale.

Pour 6 états, on a trouvé de bons "candidats", mais on n'est pas sûr d'avoir trouvé le Castor à 6 états :

En 1990pour n=6. le reccord était
95 524 079 marques en 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  
Copier

Mais en 2020 Pavel Kropitz a trouvé la machine suivante

etat     0 lu      1 lu  
1        1,d,e2    0,g,e4  
2        1,d,e3    0,d,e6  
3        1,g,e3    1,g,e1  
4        0,g,e5    1,d,STOP  
5        1,g,e6    0,d,e2  
6        0,d,e3    0,d,e5  
Copier

Cette machine s'arrète en étapes, où est la notation fléchée de Knuth.
Cf l'article de wikipedia (page web)

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.

Page écrite en 1990 mais remise à jour en 2024 !

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