Nicolas Boulay a écrit 16010 commentaires

Prend le cas d'un compilateur C de python et un code de script.

L'interprétation du script n'a rien à voir avec le programme Compilateur.

Et c'est exactement le cas pour la fonction halt() elle même. Sa sortie dépend des 2 paramètres et pas seulement du 1er.

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

Je vais leur rappeler cela. Je pense qu'ils vont adorer.

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

Et pourtant dans la 2ième données quelconque, le paramètre peut changer la réponse attendu !

Tout comme ton premier argument est un programme quelconque, qui fait tout ce qu'il veut de la donnée quelconque.

Donné quelconque qui ne se définit pourtant complètement qu'avec une autre donnée...

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

Cela serait énorme de pouvoir s'adapter à l'api de robot race, qui est une simulation de course avec une IA.

http://www.pobot.org/-Robot-Race-.html?decoupe_recherche=vir(...)

L'idée est de faire l'algo de pilotage le plus efficace. A cause du moteur physique, c'est loin d'être simple !

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

* un booléen "vrai" si quand on file a manger "donnée quelquonque" à "programme" il s'arrête

Ok. L'important c'est "quelconque".

Si on traduit pour halt(halt,halt), avec halt(halt1,halt2) en utilisant des alias pour des raisons de clarté.

halt renvoie :
* un booléen "vrai" si quand on file a manger "halt2" à "halt1", il s'arrète
* faux sinon.

Or halt2 n'a pas de paramètres définis (cela change son comportement) donc, tu prends l'ensemble des possible en compte ? En gros, tu testes tous les halt1(halt2, foo) avec foo l'ensemble des programmes possibles.

C'est la différence que je voix avec une données statique, sa signification ne change pas avec un autre paramètre.

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

Je ne comprends pas... C'est déjà le cas ! halt n'interprète pas son deuxième argument comme une fonction.

C'est là mon problème. Le premier argument s'applique sur le second, or le second pour exprimer sa signification a besoin d'un argument si il s'agit d'une fonction, que l'on peut définir comment ?

Je propose soit null, soit la fonction elle-même.

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

Comment tu veux prouver l'inexistence de quelques choses que tu ne définis pas ?

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

Le premier mot qui m'est venu à l'esprit, c'était "connard" puis je me suis dis que tu devais avoir bac+12 et moi uniquement bac+6, et je me suis demandé s'il était, sans doute possible, que je gagne le double de ton salaire. Cela m'a calmé d'un coup. Et j'ai mieux compris ton énervement.

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

La prochaine fois je dis d'accord si vous me donner la votre ? :)

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

Pour ton info, j'ai un DEA d'info passé certe il y a 7 ans.

2- Il est démontré ET il a beaucoup d'intérêts.

La démonstration que l'on me rabâche prouve que le halt() n'existe pas. Or ce halt() qui n'existe pas n'est pas ou mal définit notamment dans le cas qui intéresse pour faire la démonstration.
Donc, je demande des précisions pour savoir précisément de quoi on parle (quitte à remettre en question la démonstration que l'on me balance mais bon).

Un halt() qui prend une fonction et une donnée qui n'est pas une fonction demandant des paramètres est une restriction au halt() précédent qui reste utile. idem pour une fonction qui rend un troisième état : "cela dépend des donnés". C'est moins générique mais tout aussi utile.

Tu nous demande si ce nombre est pair ou impair, et on te dit "ca n'a pas de sens, vu qu'il n'existe pas !".

Comment pouvoir faire une démonstration par l'absurde qui infirme une hypothèse si 2 hypothèses sont absurdes ? Comment savoir laquelle est la bonne ?

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

D'après le commerçant, les loueurs qui prennent la carte magnétique notent ensuite discrètement le code qui est derrière.

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

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