Accueilretour

Le problème de l'arrêt et les castors actifs

Sémantique

Logique

Infini

Mesure

Probas

Nombres

Physique

Les propositions indécidables de Gödel ont eu de nombreux prolongements en informatique. Très tôt, avant même la conception des premiers ordinateurs, A. Turing élabora la théorie des machines de Turing, qui introduisaient des concepts encore en vigueur actuellement : entrée, sortie, mémoire et programme.

Une machine de Turing est un appareil théorique disposant d'une bande infiniment longue sur laquelle une tête peut lire et écrire, d'un registre de mémoire (fini) et d'un "processeur" capable de réaliser les opérations suivantes : 

  • déplacer la bande vers la droite / la gauche ;
  • modifier l'état du registre selon sa valeur actuelle et la valeur sur la bande ;
  • écrire ou effacer une valeurs sur la bande. 

Le traitement continue jusqu'à ce que la machine atteigne un état particulier qui provoque son arrêt -- ceci ne se produit pas forcément.

Le problème de l'arrêt consiste à déterminer, étant donné une machine de Turing et un jeu de programme / données initiales, si la machine va s'arrêter. Turing a prouvé que cette question était formellement indécidable.

En effet, les machines de Turing, comme les propositions de Gödel, peuvent se ramener à des successions de chiffres (être énumérées).

Supposons alors que le problème de l'arrêt soit décidable. Il existe donc une machine M0 qui, lorsqu'on lui fournit les instructions (le n°) d'une machine M, et une donnée initiale n, s'arrête en répondant "oui" (en écrivant 1) si M s'arrête avec la donnée n, et "non" (écrit 0) dans le cas contraire. On construit alors (rigoureusement !) une machine M1 fonctionnant comme suit. En présence d'une donnée n, M1 forme les instructions (le n°) de la machine n, suivi de n [1], puis fonctionne comme M0, à ceci près que là où M0 aurait répondu "oui", M1 calcule indéfiniment, et s'arrête en revanche là où M0 aurait répondu "non". De cette façon, M1 ne s'arrête pas si et seulement si on lui donne un n qui est le n° d'une machine qui s'arrête pour la donnée n.

Maintenant, M1 est elle-même une machine de Turing, donc porte un numéro  n1.

Alors on se rend compte de la contradiction : si l'on propose à M1 la donnée initiale n1, M1 devrait calculer sans arrêt si et seulement si n1 est le numéro d'une machine qui s'arrête pour la donnée initiale n1... mais la machine correspondant au numéro n1 est M1. M1 ne peut exister.

Ceci nous conduit droit chez les castors actifs.

Parmi les machines qui s'arrêtent, laquelle machine travaille le plus longtemps avant de s'arrêter ? Telle quelle, cette question n'a pas grand sens. Il nous faut préciser : étant donné une machine de Turing disposant de 2 symboles (0 et 1), et pouvant prendre n états, quel est le nombre maximal bb(n) de 1 que la machine peut écrire sur une bande initialement vide avant de s'arrêter ? La machine en question est alors appelée un castor actif (busy beaver, d'où la notation).

On peut estimer :


n =   0 1 2 3 4 5 6
bb(n) =   0 1 4 6 13  >4098   >136 612  

La suite de valeurs ainsi obtenue est appelée fonction σ de Rado.

Note

[1] Il y a donc deux "n" consécutifs, le premier identifiant une machine et le second un jeu de données.