Ben c'est le fait de savoir si il existe ou non (si le problème est donc décidable ou non) un algorithme/programme qui peut dire pour tout programme en entrée si il va s'arrêter ou non.
On peut résoudre le problème d'arrêt pour tous les programmes (sans "oracle") si on dispose d'un "oracle" (qui n'existe pas mais c'est pour expliquer le problème un peu plus). Mais dans ce cas on a repoussé le problème d'arrêt pour les programmes + oracle (donc notre algo de décidabilité du problème d'arrêt + oracle ne peut pas décider l'arrêt des prog+oracle)... Mais on peut le résoudre avec un algo de décidabilité + oracle pour les prog sans oracle + oracle pour les progs avec oracle... mais alors on a de nouveau repoussé le problème plus loin, cet algo ne peut décider pour ceux avec 2 oracles et ainsi de suite.
Le problème que ontologia nous donne ici est du même principe... si tu peux définir à l'avance le domaine complet pour toutes fonctions tu peux écrire un algo qui résout le problème d'arrêt... étant donné que ce n'est pas possible, l'algo que cherche ontologia n'existe pas... ça ne veut pas dire qu'on ne peut pas faire ce qu'il veut pour des cas particulier, ça veut juste dire que c'est infaisable pour le cas général.
PS: un oracle est une boite noire qui nous assure de résoudre le problème qu'elle doit résoudre... dans notre cas le problème d'arrêt. Genre un extraterrestre arrive sur terre et nous le donne et ça marche :) mais comme montré plus haut, ça ne résout pas alors le problème pour les progs+l'oracle.
[^] # Re: Halting problem
Posté par allcolor . En réponse au journal Déterminer le domaine d'un programme. Évalué à 3.
On peut résoudre le problème d'arrêt pour tous les programmes (sans "oracle") si on dispose d'un "oracle" (qui n'existe pas mais c'est pour expliquer le problème un peu plus). Mais dans ce cas on a repoussé le problème d'arrêt pour les programmes + oracle (donc notre algo de décidabilité du problème d'arrêt + oracle ne peut pas décider l'arrêt des prog+oracle)... Mais on peut le résoudre avec un algo de décidabilité + oracle pour les prog sans oracle + oracle pour les progs avec oracle... mais alors on a de nouveau repoussé le problème plus loin, cet algo ne peut décider pour ceux avec 2 oracles et ainsi de suite.
Le problème que ontologia nous donne ici est du même principe... si tu peux définir à l'avance le domaine complet pour toutes fonctions tu peux écrire un algo qui résout le problème d'arrêt... étant donné que ce n'est pas possible, l'algo que cherche ontologia n'existe pas... ça ne veut pas dire qu'on ne peut pas faire ce qu'il veut pour des cas particulier, ça veut juste dire que c'est infaisable pour le cas général.
PS: un oracle est une boite noire qui nous assure de résoudre le problème qu'elle doit résoudre... dans notre cas le problème d'arrêt. Genre un extraterrestre arrive sur terre et nous le donne et ça marche :) mais comme montré plus haut, ça ne résout pas alors le problème pour les progs+l'oracle.