Questionnement sur la preuve de l'indécidabilité algorithmique du problème de l'arrêt !

[invite05799208]

[Ceci n'est pas un troll : c'est juste une question sur une incompréhension de ma part, que je vais exposer :]

Bonjour à tous,

On peut voir une preuve de l'indécidabilité algorithmique du problème de l'arrêt sur wikipédia et wikipedia en anglais.
Ces deux preuves sont en fait la même, si je ne me trompe (celle de la version anglaise étant juste un peu plus détaillée), et il semble que cette preuve est couramment admise.

Mon problème, c'est qu'en réutilisant le même raisonnement sur des objets sensiblement différents, j'aboutis à des conclusions absurdes.
Et cependant, je n'arrive pas à voir où est l'erreur, à quel endroit ma preuve diffère en rigueur de celle du problème de l'arrêt.


Voici mon énoncé (qui est écrit dans le style de l'article en français, mais les précisions de rigueur ajoutées dans l'article anglais n'y changent rien) :



On va se restreindre à l'ensemble des fonctions qui s'arrêtent toujours (quels que soient leurs paramètres).
Soit une lettre a correspondant à une chaîne de caractère représentant le "texte" d'une fonction. J'appelle 'a' la fonction correspondante.

Soit la fonction RET(f, p), qui prend en paramètre deux chaînes f et p représentant des fonctions qui existent et qui s'arrêtent.
RET(f, p) retourne 1 si le programme correspondant 'f'(p) retourne 1, et 0 sinon. On suppose que cette fonction RET existe et s'arrête.

Remarque : Il n'importe absolument pas, ici, de savoir comment se comporte la fonction RET si on lui donne en entrée une fonction qui ne s'arrête pas, car on se contentera dans cette preuve de ne lui donner que des fonctions qui s'arrêtent.


Posons maintenant la fonction F comme suit :

function F (chaîne p) {

	si RET(p, p) = 1, alors retourne 0;

	sinon retourne 1;

}

F est bien définie et s'arrête, puisque par hypothèse, RET existe et s'arrête.

Or, si on appelle s le texte de la fonction F, que vaudrait alors F(s) ?

Si F(s) vaut 0, c'est (par définition de F) que RET(s,s) vaut 1. Or, RET(s, s) est la fonction qui retourne ce que retourne 's'(s), soit F(s)... d'où : contradiction.
Mais si F(s) vaut 1, c'est que RET(s,s), donc F(s), vaut 0 ! Contradiction.

On en déduirait donc que l'hypothèse de départ est fausse, à savoir : Soit RET n'existe pas, soit RET existe mais ne s'arrête pas.

Mais cette conclusion est absurde, puisque nous avons un exemple concret d'implémentation de RET : Il suffit, pour avoir le résultat de RET(f, p), d'exécuter la fonction 'f'(p), qui par définition s'arrête !
Donc on sait qu'il est possible de trouver une fonction RET qui donne toujours le résultat d'une fonction qui s'arrête et qu'on lui passe en paramètre (donc RET doit exister et s'arrêter...).

Ce qui entre en contradiction avec le raisonnement ci-dessus.


Avez-vous une idée de l'origine de cette absurdité ? Quel écart de rigueur ai-je fait par rapport à la preuve de l'indécidabilité du problème de l'arrêt ?

Merci pour vos réponses !
-----

[Médiat]

Bonsoir,

Il y a au moins une chose pas claire dans votre démonstration :

Soit la fonction RET(f, p), qui prend en paramètre deux chaînes f et p représentant des fonctions qui existent et qui s'arrêtent.

F est bien définie et s'arrête, puisque par hypothèse, RET existe et s'arrête.

Dans cette dernière phrase vous oubliez une hypothèse importante sur les paramètres de RET (donc de F)

Or, si on appelle s le texte de la fonction F, que vaudrait alors F(s)

Votre question n'a pas de réponse puisque vous ne savez pas si RET(s, s) existe et s'arrête (et comme elle s'appelle elle-même ...).

[invite05799208]

Bonsoir,

Soit la fonction RET(f, p), qui prend en paramètre deux chaînes f et p représentant des fonctions qui existent et qui s'arrêtent.

Par l'expression que vous avez mise en gras, voilà ce que je voulais dire :
On donne à RET un premier paramètre qui représente une fonction qui s'arrête toujours (quelque soit le paramètre) (après tout, on lui donne ce qu'on veut).
Le second paramètre est le paramètre de la fonction représentée par le premier paramètre.
'f'(p) s'arrête car on choisit f tel que 'f' s'arrête toujours.

F est bien définie et s'arrête, puisque par hypothèse, RET existe et s'arrête.

Dans cette dernière phrase vous oubliez une hypothèse importante sur les paramètres de RET (donc de F)

Oui, je pense que j'aurais dû préciser dans l'hypothèse : "RET existe et s'arrête quels que soient les arguments passés, sous réserve que ceux-ci respectent les restrictions évoquées plus haut (ie : sous réserve que 'f' s'arrête toujours)."

Ce raisonnement vous paraît-il convenable ?
Sachant que dans la preuve, les paramètres envoyés sont bien toujours tels que 'f' s'arrête, ce qui convient aux restrictions de l'hypothèse...

( Le fait que RET existe et s'arrête quel que soit son paramètre (selon les restrictions évoquées plus haut) est posé comme hypothèse dans le cadre du raisonnement par l'absurde (comme on pose l'existence de la fonction HALT). )

[invite05799208]

Màj : Après réflexion, je crois que je comprends mieux où se situerait le problème, que vous avez soulevé.
Pour que RET(p, p) finisse, il faut que 'p' finisse toujours. Donc F ne finit pas "toujours" (quel que soit le paramètre).
Donc je ne peux pas conclure ainsi sur F(s).

Il faut que je réfléchisse plus avant à cette question, demain après-midi (car il se fait tard).

[A voir en vidéo sur Futura]

[invite05799208]

Désolé pour le retard, mais je n'ai pas eu le temps de me pencher à nouveau là-dessus avant.

Bon, comme l'article de Wikipédia (voir : Problème de l'arrêt) a changé, optant pour une simplification de la démonstration, je vais en profiter pour moi-même reformuler mon truc avec des termes plus clairs (en copiant-collant le raisonnement, ne modifiant que certains éléments) :



Tout programme PROG est également une chaîne de caractères, qui représente le codage de PROG, qui sera notée prog.

Supposons par l'absurde qu'il existe un programme HALT(P,X) tel que :



On pourrait alors construire le programme DIAGONALE(X) suivant :

DIAGONALE(ch) :
Si HALT(ch,ch)=1 alors retourner 0, sinon retourner 1.

Mais, on obtient une contradiction pour l'entrée diagonale. En effet, supposons que HALT(diagonale,diagonale)=1, ce qui signifie que le programme DIAGONALE retourne 0 sur l'entrée diagonale. Dans ce cas, d'après le pseudo-code de DIAGONALE, DIAGONALE(diagonale) va retourner 1, ce qui est le contraire de l'hypothèse.

Inversement, si on suppose que HALT(diagonale,diagonale)=0, et donc que le programme DIAGONALE retourne 1 sur l'entrée diagonale, alors DIAGONALE(diagonale) va retourner 0, ce qui est également contradictoire.

[invite05799208]

Et donc, on pourrait proposer qu'alors, c'est que HALT ne retourne rien, et ne s'arrête pas.

Bon, une chose est sûre : il est possible de programmer HALT tel qu'il s'arrête quand on lui passe en paramètre un programme qui s'arrête.

De là, DIAGONALE(ch) s'arrête si CH s'arrête. Et il se peut qu'elle ne s'arrête pas si CH ne s'arrête pas.

Mais on n'a aucune info concernant DIAGONALE(diagonale), puisque tantôt DIAGONALE s'arrête, tantôt non, selon le paramètre qu'on lui donne...
D'où l'impossibilité de conclure, en fait.

Donc, cela résoudrait la question..?
Qu'en pensez-vous ?

[Médiat]

Bonjour,

Désolé pour le retard, mais je n'ai pas eu le temps de me pencher à nouveau là-dessus avant.

Pas de problème

Et donc, on pourrait proposer qu'alors, c'est que HALT ne retourne rien, et ne s'arrête pas.

Cela paraît plus que raisonable :
L'exécution de DIAGONALE(diagonale) nécessite l'exécution de
HALT(diagonale, diagonale) qui nécessite l'exécution de
DIAGONALE(diagonale)
HALT(diagonale, diagonale) qui nécessite l'exécution de
DIAGONALE(diagonale)
HALT(diagonale, diagonale) qui nécessite l'exécution de
DIAGONALE(diagonale)

...

[invite05799208]

Oui, à ceci près que l'exécution de HALT(diagonale, diagonale) ne nécessite pas, théoriquement, l'exécution de DIAGONALE(diagonale) : Le programme se débrouille comme il veut pour sortir sa réponse (il peut analyser le code d'une manière quelconque), même si ça revient peut-être, au final, à l'exécuter (? ça resterait à prouver ?).

[Médiat]

Oui, à ceci près que l'exécution de HALT(diagonale, diagonale) ne nécessite pas, théoriquement, l'exécution de DIAGONALE(diagonale) : Le programme se débrouille comme il veut pour sortir sa réponse (il peut analyser le code d'une manière quelconque), même si ça revient peut-être, au final, à l'exécuter (? ça resterait à prouver ?).

Mais cela ne tue pas la boucle infinie pour autant, car Halt doit faire plus qu'analyser le code, il doit, a minima simuler le fonctionnement de Diagonale, avec diagoanle en entrée, qui nécessite la simulation du fonctionnement de Halt quand on lui donne comme paramètres Diagonal et Diagonale, ce qui nécessite etc.