Nicolas Boulay a écrit 15824 commentaires

J'ai cherché sans trouver.

C'est lié à la loi qui dit que seul les forces de l'ordre devraient pouvoir vérifier tes papiers.

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

Il n'y a rien d'autres à ajouter là dessus.

Tu ne définis pas complètement le comportement de halt(in,in) que tu supposes exister. Je demande des précisions sur son comportement pour les fonctions demandant pour paramètre une fonction. Tu ne les donnes pas, genre halt(halt,halt) peut être équivalent à halt(halt, null) et donc à halt(null). Rien ne dit le contraire dans la démonstration.

Je ne comprends pas pourquoi halt(halt, halt) n'est pas définit donc entraîne la non existence de halt mais que halt(func,func); avec int func(int (*foo)()){if(foo()) while(1); else return 0;} n'entraine pas la non existence de func.

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

Si c'est si simple pourquoi ne répond-tu pas à mes simples interrogations ?

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

Le pire, c'est que tout le monde te dit que t'as tort, mais tu insistes.

J'ai toujours des demandes de précisions que personne m'apporte.

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

Dire à quelqu'un qui l'a tord, ne l'a jamais prouvé.

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

Devant le prochain prof de math que je rencontre, je tenterais une démonstration contenant un "de toute façon tu es trop con". Je pense qu'il saura en apprécier toute la subtilité.

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

J'ai très bien compris l'intérêt que l'on voit à ce résultat. Simplement, je n'ai pas l'impression qu'il s'applique dans un cas utile.

On démontre ça par l'absurde.

merci j'avais compris. J'ai même décortiqué les points qui me posent problème dans la démonstration sans que personne ne vienne répondre à la question.

Il n'y a toujours personne qui a répondu concernant la solution de
halt("toto(int (*foo)) {if(foo()) while(1); else return 1;}", "toto(int (*foo)) {if(foo()) while(1); else return 1;}");

En gros, le résultat d'un exemple utilisant halt sur une fonction sur elle-même, autre que halt().

Je veux juste montrer que donner une fonction ayant une fonction en paramètre à traiter (qui attend des données !), n'est pas équivalent du tout, à faire traiter une fonction et une donnés "statique".

Au mieux, on a prouvé qu'il n'existe pas de tel fonction mais rien n'interdit la fonction halt() qui prend une fonction et une donnée "statique", d''exister, celle-ci a un intérêt dans le cas de preuve pour un programme.

L'autre fonction qui a un intérêt, c'est de savoir si le code s'arrête, le code boucle, ou si l'arrêt dépend des données. Certe une telle fonction peut se construire avec le halt définit habituellement mais c'est un sur-ensemble qui inclus des cas non nécessaire. Par exemple, dans le cas halt(halt), la fonction répondrait cela dépend des données.

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

Si tu es trop bête pour ne pas voir qu'utiliser un outil (même fictif) dans une démonstration sans pouvoir en donner un seul exemple, ne sert à rien, je ne peux rien pour toi.

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

Ta démonstration par l'absurde est valide uniquement si tous les éléments sont juste. Si tu ajoutes de l'absurde, ce n'est pas étonnant que tu en es en sorti.

En gros, tu as définit halt(), je te propose de définir un exemple avec mes entrées.

Toute la démonstration repose sur le fait que halt s'avale lui-même. Si tu n'es pas capable sur un cas simple différent de halt d'estimer la sortie comment conclure quoi que ce soit sur halt lui-même ?

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

Toto prend un boolean ce qui ne vas pas avec testarray qui demande 2 fonctions.

Si tu prends

int toto (int (*foo) (void))
{
if(foo) while(1);
else return 0;
}

Je comprends que halt() est une vue de l'esprit. Par contre toto() existe et compile.

Quelle valeur va retourner halt(toto,toto); ?

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

Considère qu'elle existe et répond à ma question.

(c'est Boulay sinon)

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

Je sais bien. Je te parle de la fonction que tu as définit toi même plus haut.

Pour mémoire :

testArret(in) {
si halt(in,in) alors boucle infinie;
sinon arret;
}

testArret("testArret(in) {\n"+
"si halt(in,in) alors boucle infinie;\n"+
"sinon arret;\n"+
"}");

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

et pour testArret("toto (bool a){if(a) boucle_infinie() else arret();}"} tu dis quoi ?

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

Je dis juste que :
1- que toutes les démonstrations que l'on m'a présenté utilisent des infinis sous forme de string infinie ou de récursion infinie, ce qui est impossible avant même de pouvoir conclure sur une absurdité de l'existence de halt().

2- le "halting problem" n'a pas d'intérêt pratique, démontré ou pas

La dernière fois que j'avais parlé à un matheux de ce problème, il m'a répondu que l'on parlait du cas général, et donc de toutes les entrées possible du programme était prise en compte. D'où mon 2) et mon exemple utilisant toto et un booléen.

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

C'est bizarre c'est peut de chose pret ce que j'ai écrit dans mon long commentaire. Sauf que la conclusion est toujours la même :

"la fonction halt répond à la question si j'appelle testArret [instance A] avec en argument la string représentant le programme testArret [instance B] est-ce que testArret s'arrête."

La réponse est: cela dépend des entrées de l'instance B !

testArret("testArret(in) {\n"+
"si halt(in,in) alors boucle infinie;\n"+
"sinon arret;\n"+
"}");

C'est ici encore plus clair, qu'est-ce que tu mets dans le "in" de la 2ième fonction dans la string ?

cf mon 1er exemple idiot :

testArret("toto (bool a){if(a) boucle_infinie() else arret();}"}

testarray() ne peut pas répondre et pourtant toto est parfaitement définit et existe.

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

tu devrais tout lire :/

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

Tu ne fais que reprendre ce que j'ai écris au dessus sur la manière de comprendre halt(testArret,testArret).

Je ne vais pas tout réécrire une fois de plus. Je pose comme préalable que tout est du C normal et que halt existe.

Et si on respecte la sémantique C habituel dans le sens que tu présentes, écrire halt(testArret,testArret) veut simplement dire : est-ce que la fonction testarray de testarray de testarray de testarray de testarray de ... s'arrête or c'est une chaine infinie !

Le problème est dans la définition de ton "in".

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

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é"

Par contre il ne gère pas les plus gros modèles de chaque famille si je me rappelle bien.

je ne dis rien de plus :)

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

Cette démonstration classique est du même ordre que :

toto (bool a){
if(a) boucle_infinie() else arret();
}

? testarray(toto);

La réponse dépend des entrées,ce qui est une évidence qui n'apporte strictement aucune nouvelle information. Et d'un point de vue preuve n'a aucune utilité.

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

Et votre équipe ont des papiers la dessus ? Je serrais curieux de voir ce qui se fait sur des algo qui passe à l'échelle (et non qui explosent après 100 lignes de code).

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

https://linuxfr.org/comments/1010297.html#1010297

Merci de renforcer mon propos écrit un peu plus haut :)

halt(halt, halt) ne veut en effet rien dire car le 2 ième halt n'a de sens qu'avec ses entrées.

Le problème de l'arrêt parle donc bien d'un programme pour toutes ses entrées possibles, ce qui est une évidence dont le résultat n'a pas d'intérêt surtout si l'on considère une entrée de taille infini pour la démonstration.

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

Aprés les parties écolo, les parties libristes ?

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

Vous n'avez jamais songer à faire un produit fini comme une mini console de salon ?

J'avoue que je serais étonné de voir ce que des hackers pourraient faire avec un arm+ un gros FPGA dans le domaine du jeu vidéo.

Le plus gros spartan 3 semble couter entre 60 et 80$ l'unité. Cela commence à faire chère mais avec plus de 100 blocs multiplieur, il y a de la ressource.

Par contre, l'ISE n'est plus gratuit. Reste à mettre le plus gros, voir plusieurs version du Spartan, avec ISE gratuit. L'un uniquement pour la video et l'autre pour le reste.

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

Je dirais même plus, c'est le terme utilisé en microélectronique (avec celui de core, il me semble)

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