Le programme est fini, les entrées du programmes sont finies (même si l'ensemble des entrées possible est infini)
La question c'est : existe t'il un programme qui répond "oui, non" étant donné un programme et une entrée donnée, pour savoir si ce programme boucle ou non avec cette entrée. La réponse est "non".
Intérêt ? On aime pas avoir un programme qui boucle en général ... c'est ce qu'on appelle un "bug". Imagine un interpréteur qui te dis "ah non, t'as un problème ton programme va partir en boucle infinie". Pas d'intérêt ?
La réponse est non, dans la généralité, un tel interpréteur n'existe pas. intuitivement lui aussi risque de partir en boucle infinie avec le programme qui l'exécute sans pouvoir le détecter.
On démontre ça par l'absurde.
Et si tu veux casser la récursion c'est facile : tu files un programme sans entrées à ton interpréteur, j'ai pas vérifié mais ça ne doit pas changer grand chose à la démonstration ... Ou alors ça change tout.
2- le "halting problem" n'a pas d'intérêt pratique, démontré ou pas
Il permet de répondre "non" à Ontologia sans détours. Et à toute une famille de questions relativement identiques.
[^] # Re: Halting problem
Posté par thoasm . En réponse au journal Déterminer le domaine d'un programme. Évalué à 4.
Le programme est fini, les entrées du programmes sont finies (même si l'ensemble des entrées possible est infini)
La question c'est : existe t'il un programme qui répond "oui, non" étant donné un programme et une entrée donnée, pour savoir si ce programme boucle ou non avec cette entrée. La réponse est "non".
Intérêt ? On aime pas avoir un programme qui boucle en général ... c'est ce qu'on appelle un "bug". Imagine un interpréteur qui te dis "ah non, t'as un problème ton programme va partir en boucle infinie". Pas d'intérêt ?
La réponse est non, dans la généralité, un tel interpréteur n'existe pas. intuitivement lui aussi risque de partir en boucle infinie avec le programme qui l'exécute sans pouvoir le détecter.
On démontre ça par l'absurde.
Et si tu veux casser la récursion c'est facile : tu files un programme sans entrées à ton interpréteur, j'ai pas vérifié mais ça ne doit pas changer grand chose à la démonstration ... Ou alors ça change tout.
2- le "halting problem" n'a pas d'intérêt pratique, démontré ou pas
Il permet de répondre "non" à Ontologia sans détours. Et à toute une famille de questions relativement identiques.