Vive les castors
Non, l'informatique, ce n'est pas que Windows et ses bugs ou Mac et ses non-bugs, c'est aussi la programmation. Et la programmation, ce n'est pas qu'un écran noir devant lequel un informaticien à lunette tape d'étranges lignes de code, c'est bien plus que ça... Surtout que la programmation a été inventée avant l'informatique, grâce à Turing et sa machine...
Et les castors, dans tout ça ? Patience, ils arrivent...
Bref, une machine de Turing, qu'est ce que c'est ?
C'est une machine théorique composée
- d'un ruban (de longueur infinie, constitué de cases contenant des symboles ("0","1",...). Initialement, presque toutes les cases sont remplies de "0")
- d'une tête de lecture/écriture
- d'une table d'actions suivie par la tête de lecture.
Initialement, la tête de lecture est à la place 0 du ruban, et l'état de la machine est 0.
La machine lit alors la case sur laquelle se trouve la tête de lecture, et, suivant le symbole lu et l'état de la machine, exécute une action décrite dans la table, composée de trois étapes:
- La tête écrit un nouveau symbole sur la case où elle se trouve
- La tête effectue un mouvement vers la droite où la gauche
- L'état de la machine change
Les deux dernière étapes peuvent être remplacées par une étape "STOP" qui arrête toute exécution de la machine
En pratique, qu'est ce que ça donne ? Un petit exemple :
On part d'un ruban rempli de "0", de l'état 0, et on prend cette table d'action :
Étape 1 (état 0) : la tête est en position 0, elle lit "0". Elle va donc écrire "1", se déplacer à droite, et se mettre dans l'état 1
Étape 2 (état 1) : la tête est en position 1, elle lit "0". Elle écrit alors "1", se déplace à gauche, et revient en état 0.
Et ainsi de suite...
Rien de tel qu'une "vraie" machine de Turing pour voir ce que ce programme donne ;
Copiez-y ce programme :
0 . 1 x D
0 x 1 . D
1 . 0 x G
1 x 2 . D
2 . 0 x D
2 x 3 . =
On remarque alors que ce programme ne sert à rien, puisqu'il ne s'arrête jamais... Mais on peut tout à fait faire des programmes qui servent à quelque chose, c'est un langage de programmation comme un autre (peut-être juste un peu plus compliqué, mais pas plus limité... L'exemple du crible d'Érathostène est donné sur la page linkée). On pourrait, un jour de gros ennui, programmer Windows avec une machine de Turing...
Historiquement, la machine de Turing, concept de base de l'informatique théorique, a été inventée par Alan Turing bien avant l'invention de l'ordinateur. Elle servait alors à donner une définition d'un algorithme. Aujourd'hui, on s'en sert toujours en informatique théorique pour résoudre des problèmes de complexité ou de calculabilité.
Et cette histoire de castors, alors, qu'est ce que c'est ?
Un "castor affairé", c'est LA machine de Turing à n états et à 2 symboles ("0" et "1") qui est capable d'écrire le plus de "1" à partir d'un ruban rempli de "0", et qui s'arrête au bout d'un moment.
(Il faut imaginer tout un tas de castors occupés à grignoter des bandes selon leur ensemble de règles, et chercher le castor le plus bosseur parmis ceux-là...)
Par exemple, le castor affairé à 2 états est celui-ci :
0 . 1 x D
0 x 1 x G
1 . 0 x G
1 x 2 x =
Cette machine de Turing est capable d'écrire 4 "1", en 6 étapes.
Il est impossible de trouver une machine à 2 états et 2 symboles capable d'écrire encore plus de "1", et capable de s'arrêter seule.
Maintenant, vous pouvez tenter de trouver le castor affairé pour n=3, n=4 ou n=5... Enfin, ça, c'est ce que l'on peut penser, puisque trouver un castor affairé est quelque chose de très difficile.
Pour n=3, le castor écrira 6 "1", en 21 étapes :
0 . 1 x d
0 x 3 x d
1 . 1 x g
1 x 2 . d
2 . 2 x g
2 x 0 x g
Pour n=4, on peut trouver une machine qui peut en écrire 13, en 107 étapes :
0 . 1 x d
0 x 1 x g
1 . 0 x g
1 x 2 . g
2 . 4 x d
2 x 3 x g
3 . 3 x d
3 x 0 . d
Ces castors affairés permettent de définir la fonction de Radó et la fonction BB(n) :
Rado(n), ou Σ(n), désigne le plus grand nombre de 1 que l'on peut écrire avec une machine de Turing à n états
BB(n) (De "Busy Beaver", "Castor affairé" en anglais) ou S(n) donne le nombre d'étapes de la machine de Turing correspondant à Rado(n).
Les premiers termes sont dont :
Rado(0)=0
BB(0)=0
Rado(1)=1
BB(1)=1
Rado(2)=4
BB(2)=6
Rado(3)=6
BB(3)=21
Rado(4)=13
BB(4)=107
A première vue, ces suites n'ont pas l'air de grandir si vite que ça, et pourtant...
Pour n=5, on ne connait pas les valeurs exactes, la seule chose que l'on sait, c'est que Rado(5)>4098 BB(5)>47 176 870, record trouvé en 1989 par Marxen et Buntrock, qui tient toujours.
Pour n=6, le record date de novembre 2007 (ce mois-ci, en fait), avec Rado(6)> 2.5 × 10881 et BB(6)>8.9 × 101762.
Il est improbable que l'on connaisse un jour la valeur exacte de BB(5) ou BB(6), sans parler de BB(7) ou de BB(100)...
La particularité de ces suites, c'est qu'elles ne sont pas calculables : on ne peut pas fabriquer d'algorithme permettant d'en avoir la valeur exacte.
De plus, ces suites croissent plus vite que n'importe quelles suites calculables, comme la suite des factorielles, des suites construites avec des puissance, avec la notation de Knuth ou celle de Conway. (Rappelez-vous)
Bref... La suite BB(n) permet à coup sûr de gagner au jeu du "Mon papa, c'est le plus fort !" !
Sources :
Historique de tous les records de castors affairés.
Wikipédia, avec la preuve de l'incalculabilité de Σ(n)