thoasm a écrit 9456 commentaires

Ouais enfin un utilisateur qui tombe par hasard sur un bug rare dans une appli alors qu'il a vraiment besoin de sa machine à ce moment précis il sera bien content si elle est quand même utilisable.

Ouais, toi tu te la pêtes et tu ne fais jamais d'erreurs. Et tu es le prototype idéal.

Comme quoi les libristes sont bel et bien des trolleurs, pour plonger dedans.


Je n'adhère pas vraiment mais la sauce à l'air de prendre.

Une machine de Turing ça a pas d'IO ...


Tu oublis le cas du compilo C de l'interpréteur python qui exécute un script.

Pose bien ta question, c'est quoi le programme dont tu veux savoir si il s'arrête, et quelles sont ces données dans ce cas ? Tu peux toujours ramener ton problème à ce doublet.

Exemple : pour un compilo, ses données c'est les fichiers sources ou les fichiers objets. Il s'arrête sur une erreur ou en produisant en général du code objet.

Pour un interpréteur ses données c'est le code des fichiers du langage et éventuellement ses IOs. Il s'arrête pas si dans le code des fichiers du langage t'as un 'main(){ while(1){} ; }' ou équivalent par exemple. Il s'arrête si t'as 'main(){ return true; }' ou si t'as pas de main ou sur une erreur de syntaxe, ou sur une erreur d'IO, ...

Après pour nuancer, pour citer wp: The halting problem is, in theory if not in practice, decidable for linear bounded automata (LBAs), or deterministic machines with finite memory. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state:

C'est décidable si t'as une mémoire finie et une machine déterministe, comme nos machine à nous. Après en pratique si il faut dérouler le programme et il faut sauvegarder tous ses états pour détecter si il revient pas sur un état qu'il a déja rencontrer et donc si il boucle, c'est pas pratiquement faisable.

C'est "programme" qui donne une signification, ou pas, a donnée. Si tu lui file une (pour lui) une fonction, mais pas ses paramètres, il peut très bien t'envoyer bouler si il veut, c'est lui qui décide, et tu n'as aucun impact dessus. Dans ce cas tu dois juste deviner qu'il s'arrête.

Tu te plantes, tu mets des contraintes sur "programme".

Or il est quelquonque. C'est "programme" qui défini son comportement vis-à-vis de la donnée, qu'il peut très bien considérer comme une fonction avec des arguments si il a envie.

Et on peu lui passer n'importe quoi comme données, y compris des trucs qui n'ont pas de sens pour lui. On veut juste savoir si il veut s'arrêter. Éventuellement en te disant "t'as pas donné d'arguments à ma fonction connard", mais c'est pas nous qui décidons.

On se fiche de la signification du deuxième argument, c'est une donnée quelquonque.

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

Les spécification de halt sont très bien spécifiées, rigoureusement, logiquement et tout.
halt prend : un programme, une donnée quelquonque.
halt renvoie :
* un booléen "vrai" si quand on file a manger "donnée quelquonque" à "programme" il s'arrête
* faux sinon.

"programme" peut s'arrêter dans l'état sur une erreur genre "donnée incorrecte" "j'ai pas les paramètres, je peux rien faire connard" "ça marche c'est cool" "42" ... on s'en fout, on veut juste savoir si il s'arrête ou pas. Dans ces cas là, il s'arrête.

Il n'existe aucun programme qui respecte ces spécifications. Parce que quelle que soit le programme, on peut toujours construire un autre programme à partir de celui là de manière à ce que ces spécification soient violées. Qu'est-ce qui n'est pas défini là dedans ? Le code de la fonction "halt" ? ben ... on voulait justement savoir si il était possible de l'écrire ou non, la réponse est "non".

Ouais, amha il faudrait avoir un brevet pour l'utilisation de cet ensemble de brevets ensemble, justement.


(je suis pas juriste mais ça me semblerait logique)

Il est bon que parfois les deux se remettent en question, c'est l'évidence même.

Après quand le maître ne comprends pas ou veut en venir l'élève, c'est plus forcément de sa faute ...

Tes interrogations sont à côté de la plaque, c'est tout.

La preuve est simple, correcte, bien fondée mathématiquement et logiquement, connue et archi connue.

Et tes questions n'ont rien à y faire, elles n'ont aucun sens dans le cadre de la preuve. Voire aucun sens du tout.

C'est difficile de répondre à des questions qui n'ont pas de sens, il faut rentrer dans ta tête pour essayer de comprendre ce que tu voulais dire, sachant que c'est pas clair probablement dans ta tête non plus ... sinon ce serait plus simple pour tout le monde.

Non, ce programme ne compile pas, il n'a pas de fonction "main", déja.

Si elle existe, on a des contradictions, donc elle n'existe pas. C'est tout.

Il n'y a aucune utilisation d'une string infinie.

Le programme est fini, les entrées du programmes sont finies (même si l'ensemble des entrées possible est infini)

La question c'est : existe t'il un programme qui répond "oui, non" étant donné un programme et une entrée donnée, pour savoir si ce programme boucle ou non avec cette entrée. La réponse est "non".




Intérêt ? On aime pas avoir un programme qui boucle en général ... c'est ce qu'on appelle un "bug". Imagine un interpréteur qui te dis "ah non, t'as un problème ton programme va partir en boucle infinie". Pas d'intérêt ?

La réponse est non, dans la généralité, un tel interpréteur n'existe pas. intuitivement lui aussi risque de partir en boucle infinie avec le programme qui l'exécute sans pouvoir le détecter.

On démontre ça par l'absurde.

Et si tu veux casser la récursion c'est facile : tu files un programme sans entrées à ton interpréteur, j'ai pas vérifié mais ça ne doit pas changer grand chose à la démonstration ... Ou alors ça change tout.

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

Il permet de répondre "non" à Ontologia sans détours. Et à toute une famille de questions relativement identiques.

Ouais alors il faut se rendre à l'évidence, soit tu t'exprimes pas bien et personne comprends ce que tu veux dire, soit quelque part tu as tort, soit le problème de l'arrêt n'en est pas un, ce qui reviendrait à ce que des générations d'informaticiens aient tort, et là t'as intérêt à bien faire comprendre ce que tu veux dire si tu veux pas te faire descendre ;)



En gros, tu veux en venir ou ? Cette preuve montre qu'il existe au moins un programme dont l'arrêt est indécidable, et sûrement une infinité d'autres.

Donc t'as démontré que le problème dans sa généralité était insoluble. Après en se restreignant à des sous classes du problème effectivement on peut faire des trucs, mais bon, ces classes sont pas forcément toutes intéressantes, et surtout t'as des tas de cas intéressants qui sont pas dedans ...

Je sais bien, mais moi si.

Je les dis quand c'est approprié, je les cache pas, globalement tu dois savoir si je suis d'accord, pas d'accord ou nuancé à propos d'une idée. Je pense pas être ambigu. Toi, si.

Le problème de l'arrêt c'est pour toutes les entrées possibles, pas que pour "halt" lui même ...

En gros, ça donne halt : programme , donnee -> booleen

T'as pas de récursion ici, tu veux savoir si "donnee" s'arrête pour toutes les entrées possibles, quasiment.

d'ailleurs ta récursion n'a pas de sens, halt(halt,halt) renvoie un booleen, et ce que tu veux faire manger à ton programme c'est un autre programme.

Oh non, on note juste que t'es assez frileux sur le sujet.

On savait déja que t'étais nationaliste plutôt admirateur de gens comme Alain de Benoist, par exemple.
Après ça ne nuit pas de connaître ses interlocuteurs.

Héhé, et toi alors, tu viens faire quoi là dedans ?

( hop, ça c'est fait ---------->[] )

On parlait de psychotage ...

Il répondait à Moogle, c'était juste une remarque en passant.

Après tu le prends personnellement, ou pas. Passionnel on disait ?

Tu ne connais pas mes idées. Tu fantasmes tout seul et c'est moi qui psychote ?

Tu joues au chat et à la souris et tu te gardes bien de les énoncer.

Je serais prétentieux si je prétendais le contraire, car c'est un maître en la matière.

Héhé, déja lui il argumente ... ce qui n'est pas vraiment ton cas.

C'est intéressant, et il argumente son point de vue carrément mieux que toi.

Faudrait un peu de temps pour développer et analyser un peu tout ça, j'ai pas lu grand chose (en particulier une interview de lui [1] , et je me pose quelques questions du coup.)

A relire à froid pour une critique plus approfondie ...



[1] http://www.lepoint.fr/actualites-chroniques/jean-claude-mich(...)

J'en ai marre de répéter la même chose tout le temps. Dire "il a été prouvé que ..." c'est aller bien plus loin que simplement exprimer des doutes.