halt est une fonction dont on veut savoir si elle peut exister... donc pour la démonstration (par l'absurde, car on va tirer une contradiction)
Supposons que halt existe (on s'en fou du code ce n'est pas l'important, on suppose juste que c'est possible d'écrire une telle fonction et qu'elle est dispo).
Donc on peut écrire le programme testArret qui appel halt:
testArret(in) {
si halt(in,in) alors boucle infinie;
sinon arret;
}
Appelons ce programme avec testArret en paramètre (ce que tu donnes ce n'est pas un pointeur de testArret mais la string représentant testArret, halt étant censé répondre si oui on non la string représantant le programme avec l'entrée qu'on donne va s'arrêter ou non).
ça appelle donc halt(testArret,testArret).
Si halt(testArret,testArret) repond que le programme testArret qui prend en argument lui-même s'arrête alors je fais une boucle infinie contradisant le fait que halt a dit que testArret avec testArret en paramètre s'arrêtait.
Si halt(testArret,testArret) repond que le programme testArret qui prend en argument lui-même ne s'arrête pas alors je m'arrête contradisant le fait que halt a dit que testArret avec testArret en paramètre ne s'arrêtait pas.
Il n'y a aucune entrée infinie... nada.
Tout ce que ça montre c'est que l'hypothèse comme quoi il est possible d'écrire la fonction halt est fausse.
[^] # Re: Halting problem
Posté par allcolor . En réponse au journal Déterminer le domaine d'un programme. Évalué à 3.
halt est une fonction dont on veut savoir si elle peut exister... donc pour la démonstration (par l'absurde, car on va tirer une contradiction)
Supposons que halt existe (on s'en fou du code ce n'est pas l'important, on suppose juste que c'est possible d'écrire une telle fonction et qu'elle est dispo).
Donc on peut écrire le programme testArret qui appel halt:
testArret(in) {
si halt(in,in) alors boucle infinie;
sinon arret;
}
Appelons ce programme avec testArret en paramètre (ce que tu donnes ce n'est pas un pointeur de testArret mais la string représentant testArret, halt étant censé répondre si oui on non la string représantant le programme avec l'entrée qu'on donne va s'arrêter ou non).
ça appelle donc halt(testArret,testArret).
Si halt(testArret,testArret) repond que le programme testArret qui prend en argument lui-même s'arrête alors je fais une boucle infinie contradisant le fait que halt a dit que testArret avec testArret en paramètre s'arrêtait.
Si halt(testArret,testArret) repond que le programme testArret qui prend en argument lui-même ne s'arrête pas alors je m'arrête contradisant le fait que halt a dit que testArret avec testArret en paramètre ne s'arrêtait pas.
Il n'y a aucune entrée infinie... nada.
Tout ce que ça montre c'est que l'hypothèse comme quoi il est possible d'écrire la fonction halt est fausse.