Castor affairé - Définition
La liste des auteurs de cet article est disponible ici.
Le problème du castor affairé
Maintenant que vous êtes devenu un très bon joueur, nous vous proposons de prendre la place de l'arbitre. Des joueurs vont vous soumettre leur liste d'instructions, et vous aimeriez déterminer:
- Quels sont les joueurs éliminés car ne respectant pas la quatrième règle (la machine doit s'arrêter un jour)
- Quel est le meilleur joueur, quel est le score de chaque joueur
- Le meilleur joueur peut il recevoir le titre de "castor affairé" ? (c'est-à-dire qu'il a trouvé la liste d'instructions qui donne le meilleur score)
Ceci est un défi à la calculabilité. On peut démontrer que dans le cas général, on ne peut pas répondre algorithmiquement à la troisième question, car la fonction qui prend comme donnée une machine et répond si elle est ou n'est pas un castor affairé ne peut pas être décrite par un algorithme (par une machine de Turing par exemple). Comme conséquence, on peut affirmer que mêmes les ordinateurs les plus puissants ne pourront jamais décerner le titre de castor affairé à une machine. D'ailleurs dès la valeur 10 (et probablement même bien avant !) et même en utilisant des astuces et des procédés ad hoc c'est sans espoir.
Fonction du castor affairé
Ce qui suit est l'approche formelle du problème.
On voit qu'il n'existe qu'un nombre fini de machines de Turing à n états et 2 symboles. De plus, il est facile de démontrer que certaines s'arrêtent (tout simplement une machine qui écrit 1 puis s'arrête immédiatement après la première action). Maintenant, définissons:
- En l'ensemble fini et non vide des machines de Turing à n états et 2 symboles qui finissent par s'arrêter ;
- σ(M) (M étant un élément de En) comme le nombre de 1 écrits par la machine M avant de s'arrêter ;
- Σ(n) comme étant le maximum de σ sur En ; Σ est la fonction du castor affairé.
Σ est totale et monotone. Elle est totale, car elle est manifestement définie pour tout n ≥ 1, et elle est monotone car on a la certitude que Σ(n) < Σ(n + 1) (si on augmente le nombre d'états permis, cela induit forcément que l'on peut produire plus de 1).
Radó a prouvé que Σ n'est pas calculable ; toutefois, sa valeur est connue pour certains cas particuliers (le plus évident étant Σ(1) = 1, et on peut montrer Σ(2) = 4, Σ(3) = 6 et Σ(4) = 13), et dans d'autres cas la valeur est minorée (il suffit de trouver un exemple pour lequel la machine s'arrête, le nombre de 1 écrits étant donc un minorant).
Preuve de l'incalculabilité de Σ
Il existe plusieurs moyens de prouver l'incalculabilité de Σ, l'un d'entre eux étant d'utiliser la fonction de combinaison des machines de Turing.
Hypothèse de départ : supposons que Σ soit calculable.
Si Σ est calculable, alors la fonction D définie par D(n) = Σ(2n) l'est également. Si la fonction D est calculable, alors elle peut être représentée à l'aide d'une machine de Turing, que nous appellerons Md, et qui possédera un nombre fini d'état k (que nous ne connaissons pas).
Prenons maintenant la fonction u(f(n)) = f(n), qui se contentera d'afficher la valeur de retour d'une certaine fonction passée en paramètre. À l'instar de la fonction D, cette fonction u peut être représentée par une machine de Turing, que nous appellerons Mu. On prendra note qu'il est possible de coder cette machine Mu en utilisant n états (nous pourrions l'implémenter en moins que cela, mais cela ne nous intéresse pas dans le cadre de cette preuve).
Définissons maintenant la machine M, qui est une composition des machines Mu et Md. Autrement dit, nous allons passer en paramètre de la fonction u la fonction D afin de réaliser l'opération u(D(n)). Du fait de la composition, cette machine M sera composée de n + k états et, conformément aux descriptions précédentes, écrira sur une bande vierge D(n) = Σ(2n) symboles 1.
En résumé, nous avons obtenu une machine de Turing de n + k états et qui produit Σ(2n) symboles. Que pouvons-nous dire sur la valeur de Σ(n + k), qui est le nombre de 1 pouvant être écrits avec n + k états ? Eh bien, nous pouvons affirmer que cette fonction retournera une valeur plus grande ou en tout cas égale au nombre de 1 écrits par la machine M, c'est-à-dire : Σ(n + k) ≥ Σ(2n).
Selon l'aspect monotone de Σ, on peut affirmer la chose suivante : pour tout k < n, Σ(2n) > Σ(n + k). Cette inéquation, combinée avec celle obtenue précédemment, nous donne : Σ(2n) > Σ(n + k) ≥ Σ(2n) | k < n.
Cette évidente contradiction nous permet d'affirmer que notre hypothèse de départ était fausse, Σ n'est pas calculable.
