Ça fait deux jours qu’on te le répète : il n’y a pas de chaîne infinie !
On la refait, je vais essayer de le faire C-like vu que tu sembles aimer ça.
La fonction halt() prend une fonction F et un paramètre quelconque P et doit dire si la fonction F termine avec P comme paramètre. typedef void* (*fonction_t)(void*);
bool halt(fonction_t f, void* p);
Pour l’instant, ça va ?
Bon. C’est tout ce qu’on a besoin de définir pour halt() : on cherche à savoir si une fonction qui fait ça peut exister. Donc, par l’absurde, on fait comme si, et on cherche une contradiction. Et on se dit, tiens, si on écrivait une fonction (= un (bout de) programme) void foutlebordel(fonction_t fn) {
if (halt(fn, code_de(fn)))
while (1);
}
et si on la passait à halt() ?
Et, pensé-je, là où tu coinces, c’est que code_de(fn), c’est fn : une fonction (ou un programme), c’est du code (des octets qui seront interprétés par le processeur / la machine de Turing). Passer un pointeur de fonction sur la fonction foutlebordel, c’est indiquer où se trouve son code (= une suite d’octets) en mémoire, c’est donc comme donner son code directement. (Évidemment, pour nous, humains, c’est plus facile de lire du code en C que les 500 octets correspondant en binaire, mais pour une machine et pour la démonstration, c’est pareil.)
Donc, foutlebordel(foutlebordel) va appeler halt(foutlebordel, code_de(foutlebordel)), c’est-à-dire la même chose que halt(foutlebordel, foutlebordel).
On ne sait pas ce que halt fait avec foutlebordel. On ne sait pas si elle essaie de l’exécuter (on se doute que non vu que halt ne s’arrêterait pas si la fonction ne s’arrêtait pas). On peut penser que halt fait de l’analyse statique de code (comme un compilateur).
On se fout de savoir ce que halt fait avec foutlebordel. On veut juste que ça foute le bordel.
Or donc, halt(foutlebordel, foutlebordel) va nous dire si un appel de foutlebordel(foutlebordel) s’arrêterait. Je rappelle que foutlebordel(foutlebordel) est justement ce qu’on est en train d’exécuter.
Donc, si halt(foutlebordel, foutlebordel) répond :
— vrai, foutlebordel(foutlebordel) part en boucle infinie. Donc halt se trompe ;
— faux, foutlebordel(foutlebordel) s’arrête. Donc halt se trompe.
Donc, si halt existe, halt se trompe sur foutlebordel(foutlebordel). Donc halt ne peut exister.
[^] # Re: Halting problem
Posté par Sylvain Sauvage . En réponse au journal Déterminer le domaine d'un programme. Évalué à 6.
On la refait, je vais essayer de le faire C-like vu que tu sembles aimer ça.
La fonction halt() prend une fonction F et un paramètre quelconque P et doit dire si la fonction F termine avec P comme paramètre.
typedef void* (*fonction_t)(void*);
bool halt(fonction_t f, void* p);
Pour l’instant, ça va ?
Bon. C’est tout ce qu’on a besoin de définir pour halt() : on cherche à savoir si une fonction qui fait ça peut exister. Donc, par l’absurde, on fait comme si, et on cherche une contradiction. Et on se dit, tiens, si on écrivait une fonction (= un (bout de) programme)
void foutlebordel(fonction_t fn) {
if (halt(fn, code_de(fn)))
while (1);
}
et si on la passait à halt() ?
Et, pensé-je, là où tu coinces, c’est que code_de(fn), c’est fn : une fonction (ou un programme), c’est du code (des octets qui seront interprétés par le processeur / la machine de Turing). Passer un pointeur de fonction sur la fonction foutlebordel, c’est indiquer où se trouve son code (= une suite d’octets) en mémoire, c’est donc comme donner son code directement. (Évidemment, pour nous, humains, c’est plus facile de lire du code en C que les 500 octets correspondant en binaire, mais pour une machine et pour la démonstration, c’est pareil.)
Donc, foutlebordel(foutlebordel) va appeler halt(foutlebordel, code_de(foutlebordel)), c’est-à-dire la même chose que halt(foutlebordel, foutlebordel).
On ne sait pas ce que halt fait avec foutlebordel. On ne sait pas si elle essaie de l’exécuter (on se doute que non vu que halt ne s’arrêterait pas si la fonction ne s’arrêtait pas). On peut penser que halt fait de l’analyse statique de code (comme un compilateur).
On se fout de savoir ce que halt fait avec foutlebordel. On veut juste que ça foute le bordel.
Or donc, halt(foutlebordel, foutlebordel) va nous dire si un appel de foutlebordel(foutlebordel) s’arrêterait. Je rappelle que foutlebordel(foutlebordel) est justement ce qu’on est en train d’exécuter.
Donc, si halt(foutlebordel, foutlebordel) répond :
— vrai, foutlebordel(foutlebordel) part en boucle infinie. Donc halt se trompe ;
— faux, foutlebordel(foutlebordel) s’arrête. Donc halt se trompe.
Donc, si halt existe, halt se trompe sur foutlebordel(foutlebordel). Donc halt ne peut exister.
Ça va mieux ou on va tous se tirer une balle ?