Le résultat de halt sur ton exemple précis est simple, c'est 1.
En effet, toto, lorsqu'on lui file comme entrée une chaîne de caractères (le deuxième argument) va l'interpréter comme un pointeur foo sur une fonction (puisque c'est ton but), Or c'est une chaine de caractères, pas du tout un pointeut vers une fonction et l'appel foo va segfaulter. Conclusion l'appel de halt va répondre 1, puisque la fonction va s'arreter (en segfaultant)
l'analogie du post auquel tu réponds est mauvaise. Ce qui fait marcher le théorème de l'arrêt, c'est justement qu'on peut considérer un programme également comme des données.
Suppose que tu aies réussi à écrire une fonction (en C) halt2 qui prend une chaîne de caractères représentant une fonction C (à une variable, une chaîne de caractères) en argument et une chaîne de caractères et qui fait la chose suivante:
- 1 si la fonction C s'arrête lorsqu'on l'exécute sur l'argument et qu'il répond 0
- 0 dans tous les autres cas
Maintenant on considère la fonction halt1 définie comme suit
int halt1(char *x)
{
return halt2(x,x);
}
Ta fonction halt1 est écrite en C, donc elle est représentée par une chaîne de caractères
(les quelques caractères écrits plus haut, dans lesquels on aura en gros remplacé l'appel à halt2 par le contenu de halt2), qu'on va appeller t;
Maintenant, rien n'interdit d'exécuter halt1(t). Et là que se passe-t-il ?
Vu qu'elle se contente d'appeller halt2 qui répond toujours, le résultat devrait être soit 0, soit 1. Si elle répond 1, c'est à dire halt2(t,t) vaut 1, cela signifie que la fonction représentée par t, lorsqu'on l'appelle avec l'argument t s'arrete et repond 0. Mais la fonction representée par t, c'est justement halt1, donc ca signifie que halt1 lorsqu'on l'appelle avec l'argument t s'arrête et répond 0. Contradiction.
Le cas avec 1 se règle de la même manière.
On arrive donc à une contradiction. D'où provient-elle ? Du fait qu'une telle fonction halt2 est impossible à écrire.
[^] # Re: Halting problem
Posté par Nimmy . En réponse au journal Déterminer le domaine d'un programme. Évalué à 1.
En effet, toto, lorsqu'on lui file comme entrée une chaîne de caractères (le deuxième argument) va l'interpréter comme un pointeur foo sur une fonction (puisque c'est ton but), Or c'est une chaine de caractères, pas du tout un pointeut vers une fonction et l'appel foo va segfaulter. Conclusion l'appel de halt va répondre 1, puisque la fonction va s'arreter (en segfaultant)
Mais je vois pas en quoi tout cela peut t'aider.
[^] # Re: Halting problem
Posté par Nimmy . En réponse au journal Déterminer le domaine d'un programme. Évalué à 3.
[^] # Re: Halting problem
Posté par Nimmy . En réponse au journal Déterminer le domaine d'un programme. Évalué à 4.
Suppose que tu aies réussi à écrire une fonction (en C) halt2 qui prend une chaîne de caractères représentant une fonction C (à une variable, une chaîne de caractères) en argument et une chaîne de caractères et qui fait la chose suivante:
- 1 si la fonction C s'arrête lorsqu'on l'exécute sur l'argument et qu'il répond 0
- 0 dans tous les autres cas
Maintenant on considère la fonction halt1 définie comme suit
int halt1(char *x)
{
return halt2(x,x);
}
Ta fonction halt1 est écrite en C, donc elle est représentée par une chaîne de caractères
(les quelques caractères écrits plus haut, dans lesquels on aura en gros remplacé l'appel à halt2 par le contenu de halt2), qu'on va appeller t;
Maintenant, rien n'interdit d'exécuter halt1(t). Et là que se passe-t-il ?
Vu qu'elle se contente d'appeller halt2 qui répond toujours, le résultat devrait être soit 0, soit 1. Si elle répond 1, c'est à dire halt2(t,t) vaut 1, cela signifie que la fonction représentée par t, lorsqu'on l'appelle avec l'argument t s'arrete et repond 0. Mais la fonction representée par t, c'est justement halt1, donc ca signifie que halt1 lorsqu'on l'appelle avec l'argument t s'arrête et répond 0. Contradiction.
Le cas avec 1 se règle de la même manière.
On arrive donc à une contradiction. D'où provient-elle ? Du fait qu'une telle fonction halt2 est impossible à écrire.