Re: Halting problem

On arrive donc à une contradiction. D'où provient-elle ? Du fait qu'une telle fonction halt2 est impossible à écrire.

Et le fait que t soit de taille infinie, on s'en tape ?

Soit la fonction halt(void (* foo)(void *), void * data); qui est notre oracle.

void halt1 (char * blob)
{
void (* foo)(void *) = slice_prog(blob);
void * data = slice_data(blob);
if ( halt( foo, data)) { while(1); }
}

Jusque là, on a écrit la même chose.

Ensuite, tu propose d'écrire

void halt_2( void (* foo)(void *) )
{
char * blob;
memcpy(blob, foo, sizeof(foo));
halt1(blob);
}

void Montest_de_halt()
{
halt_2(halt1);
}

On l'exécution on aura:

Montest_de_halt();
..halt_2(halt1);
....halt1(blob(halt1));
......halt(halt1, null);

Comme halt(null) ==1,
donc halt1(null) boucle,

donc halt(halt1,null) == 0,
donc halt1(blob(halt1)) ne boucle pas.

Et le plan d'exécution de montest_de_halt() se déroule sans accroc.

Il n'y a rien de contradictoire la dedans.

Souvent on me propose comme exemple halt(halt,halt) (que tu appelles halt2(t,t)). Qu'est-ce que cela signifie ?

Cela signifie que je veux savoir si halt (instance A) s'arrête avec la fonction halt (instance B) en entrée sans préciser l'entrée de l'instance B. Erreur de compile.

Si on considère que halt(halt, halt) est en fait, la fonction qui test l'arret de halt (instance B) ayant halt (instance C)en entrée qui elle même prend halt (instance C) et ainsi de suite, je créait ainsi une suite infini.

Comme le résultat final dépend du nombre pair ou impair d'instance de "halt" considérée, je ne peux pas répondre puisque que ce nombre est infini. Je n'ai donc toujours rien prouvé sur l'existence de "halt".

"La première sécurité est la liberté"