Répondre à la discussion
Page 1 sur 6 12 3 4 5 DernièreDernière
Affichage des résultats 1 à 30 sur 178

indécidabilité de la décidabilité

  1. #1
    ilelogique

    indécidabilité de la décidabilité

    Bonjour,
    Lorsqu'on a posé un langage, une théorie et des règles de déduction je vois trois catégories d'énoncés exprimables dans le langage et c'est le troisième qui m'ennuie :
    - les énoncés décidables
    - les énoncés indécidables
    - les énoncés desquels on ne sait pas encore si ils sont décidables ou pas.

    La question :
    existe-t-il des énoncés pour lesquels on a prouvé que la décidabilité est indécidable ???
    presque autrement dit : a-t-on prouvé que tout énoncé est soit décidable soit indécidable ? (ou bien cela dépend-il de la théorie, de la richesse du langage ?)

    pour être franc c'est la chaîne infinie qui se profile qui me donne le vertige :
    Car alors existerait-il des énoncés pour lesquels on ne pourrait pas décider si la décidabilité est décidable ou pas ? Etc ??

    Si des fois vous en savez un peu là dessus je serais ravi de le savoir,
    merci à tous.

    -----

    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  2. Publicité
  3. #2
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    La question :
    existe-t-il des énoncés pour lesquels on a prouvé que la décidabilité est indécidable ???
    Problème de l’arrêt non ? Mais au vue de la contradiction de l'énoncé je dois ciblé à coté

    Patrick
    Dernière modification par invite6754323456711 ; 14/07/2013 à 19h57.

  4. #3
    Paraboloide_Hyperbolique

    Re : indécidabilité de la décidabilité

    Erreur, énoncé initial mal lu
    Dernière modification par Paraboloide_Hyperbolique ; 14/07/2013 à 20h12.

  5. #4
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Bonsoir

    Il y a aussi cet article de vulgarisation Presque tout est indécidable ! de Jean-Paul DELAHAYE

    Patrick

  6. #5
    ilelogique

    Re : indécidabilité de la décidabilité

    Bonjour merci pour vos réponses, pas de souci pour vos erreurs, le lien donné n'est pas bon, mais svp :
    Je parlais surtout de la réponse à la question que je pose svp???
    merci,
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  7. #6
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    Je parlais surtout de la réponse à la question que je pose svp???
    faudrait alors plus formaliser ce qui pour vous est décidable de ce qui ne l'ai pas. Vous écrivez : existe-t-il des énoncés pour lesquels on a prouvé que la décidabilité est indécidable ???

    Les pointeurs qui sont fournis définissent, au préalable, un cadre formel dans lequel on peut donner sens à ces étiquetages. Tandis que vous vous nous donné aucun cadre et donc chacun peut l’interpréter en fonction de ses grilles sensorielles.

    Patrick
    Dernière modification par invite6754323456711 ; 15/07/2013 à 10h23.

  8. #7
    ilelogique

    Re : indécidabilité de la décidabilité

    Bonjour,
    j'emploie le mot décidable au sens usuel.
    Dès lors qu'on s'est donné un langage, une théorie (à savoir un système axiomatique) et des règles de déduction (règles d'inférences) on peut formuler des énoncés dans le langage, un énoncé F est décidable dès lors qu'il existe une démonstration de F ou de nonF,
    Cet énoncé F est indécidable si on a prouvé que F n'est pas décidable.
    or le théorème d'incomplétude de Gödel a montré que toute théorie contenant l'arithmétique était incomplète, à savoir qu'il existe des énoncé indécidables à partir de la théorie.
    Je pensais que vous saviez ça.
    Donc je demande bien si il existe ou pas des énoncés dont la décidabilité n'est pas décidable.
    En quoi ce que je demande n'est-il pas clair ?
    Merci.
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  9. #8
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    Je pensais que vous saviez ça.
    Donc je demande bien si il existe ou pas des énoncés dont la décidabilité n'est pas décidable.
    Je vous est donné des pointeurs donc l'exemple de la décidabilité de l’arrêt qui ne demande qu'a vous d'approfondir. Avec l'article de Jean-Paul DELAHAYE qui fait référence aux travaux de Levin qui ont montré que même si on ajoute une infinité d’axiomes par un processus probabiliste le résultat sera toujours une théorie incomplète. Vous me répondez avec votre verbiage arrogant.

    Vous cherchez quoi au juste ?

    Patrick

  10. #9
    karlp

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    Bonjour,
    Lorsqu'on a posé un langage, une théorie et des règles de déduction je vois trois catégories d'énoncés exprimables dans le langage et c'est le troisième qui m'ennuie :
    - les énoncés décidables
    - les énoncés indécidables
    - les énoncés desquels on ne sait pas encore si ils sont décidables ou pas.

    La question :
    existe-t-il des énoncés pour lesquels on a prouvé que la décidabilité est indécidable ???
    presque autrement dit : a-t-on prouvé que tout énoncé est soit décidable soit indécidable ? (ou bien cela dépend-il de la théorie, de la richesse du langage ?)

    pour être franc c'est la chaîne infinie qui se profile qui me donne le vertige :
    Car alors existerait-il des énoncés pour lesquels on ne pourrait pas décider si la décidabilité est décidable ou pas ? Etc ??

    Si des fois vous en savez un peu là dessus je serais ravi de le savoir,
    merci à tous.
    Bonjour

    Sauf erreur de ma part, c'est toujours relativement à une axiomatique qu'une question est décidable ou non.
    Si, par exemple, vous posez dans un système donné comme axiome que le successeur du cardinal des entiers naturels est le cardinal des réels, alors l'hypothèse du continu est démontrable dans ce système (et est donc décidable).

    Si votre question est "existe t'il une procédure permettant de dire pour tout système si un énoncé quelconque y est décidable ou non ?" alors je crois qu'effectivement on retrouve le problème de l'arrêt de Turing. Mais je vous confesse ma grande ignorance sur le sujet.
    Très naïvement je serais porté à croire que cette procédure doit elle même être un énoncé d'un système complet .

    Je serai très heureux d'avoir l'éclairage d'un grand logicien (comme Médiat par exemple )

  11. #10
    ilelogique

    Re : indécidabilité de la décidabilité

    Mais enfin, je ne suis pas arrogant mais je ne comprends pas que personne ne semble comprendre ma question !
    je connais les théoremes de godel et je sais bien que toute théorie contenant l'arithmétique est incomplete et je ne parle pas du probleme de l'arret !

    je demande si il existe des énoncés (dans une certaine théorie, c'est à dire une axiomatique oui) dont la décidabilité est indécidable ( c'est à dire un enoncé pour lequel on aurait prouvé qu'il n'est pas possible de savoir si il est décidable ou pas )

    merci
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  12. #11
    shokin

    Re : indécidabilité de la décidabilité

    Il me semble qu'il y a les conjectures, dont on n'a encore rien pu démontrer, ni qu'elles sont décidables ni qu'elles sont indécidables.

    Dans l'article sur la décidabilité, des exemples de problèmes indécidables sont énoncés.

    Citation Envoyé par ilelogique Voir le message
    Cet énoncé F est indécidable si on a prouvé que F n'est pas décidable.
    or le théorème d'incomplétude de Gödel a montré que toute théorie contenant l'arithmétique était incomplète, à savoir qu'il existe des énoncé indécidables à partir de la théorie.
    Je pensais que vous saviez ça.
    Donc je demande bien si il existe ou pas des énoncés dont la décidabilité n'est pas décidable.
    Si la décidabilité d'un énoncé est indécidée, comme pour les conjectures, cette indécidabilité est encore plus indécidable. Tant qu'on ne sait rien, il y a toujours une part possible d'indécidabilité, une part qui ne pourra pas être démontrée. Autrement dit, si on arrivait à démontrer que la décidabilité d'un énoncé était indécidable, il y aurait quand même une part de décidabilité, puisqu'on a réussi à le démontrer. Je ne suis pas un spécialiste, mais ça me semble contradictoire. On peut aller "à l'infini", il me semble, le problème va demeurer le même. "L'indécidabilité de l'indécidabilité de l'indécidabilité de ... est-elle indécidable ?"

    Où est Médiat ?
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  13. #12
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message

    je demande si il existe des énoncés (dans une certaine théorie, c'est à dire une axiomatique oui) dont la décidabilité est indécidable ( c'est à dire un enoncé pour lequel on aurait prouvé qu'il n'est pas possible de savoir si il est décidable ou pas )
    1/ Décidabilité logique : Une proposition (on dit aussi énoncé) est dite décidable dans une théorie axiomatique, si on peut la démontrer ou démontrer sa négation dans le cadre de cette théorie.
    Un énoncé mathématique est donc indécidable dans une théorie s'il est impossible de le déduire, ou de déduire sa négation, à partir des axiomes. L'âge du capitaine d'un bateau est indécidable en fonction du tonnage et de la vitesse du navire.


    2/ Décidabilité algorithmique : Un problème de décision est dit décidable s'il existe un algorithme, une procédure mécanique qui termine en un nombre fini d'étapes, qui le décide, c'est-à-dire qui réponde par oui ou par non à la question posée par le problème.
    S'il n'existe pas de tels algorithmes, le problème est dit indécidable. Par exemple, le problème de l'arrêt est indécidable.


    Je ne comprend toujours pas votre troisième cas.

    Patrick
    Dernière modification par invite6754323456711 ; 15/07/2013 à 16h48.

  14. #13
    ilelogique

    Re : indécidabilité de la décidabilité

    Re
    oui ce serait bien si Médiat passait par là,
    karlp commence à voir ce que je veux savoir.
    Par exemple on ne sait toujours pas si la conjecture de Syracuse est décidable ou non dans l'arithmétique.
    Ma question est de savoir si on en sera forcément sûr un jour.

    C'est à dire, il y a des énoncés décidables, d'autres non et 3e cas : d'autres dont on ne sait pas
    ma question est de savoir si il existe un exemple d'énoncé dont on aurait démontré qu'on ne pourra jamais savoir si il est décidable ou pas.
    En gros dont la décidabilité serait indécidable (mais on aurait alors bien, en effet, obtenu la décidabilité de l'indécidabilité de la décidabilité oui !)


    Oui, comme je l'ai dit dans mon premier message ca pourrait partir à l'infini
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  15. #14
    shokin

    Re : indécidabilité de la décidabilité

    Je ne suis pas capable de les démontrer, mais il semble qu'il y en a ici, dans la partie "Exemples de problèmes indécidables" (qui étaient des conjectures avant que des personnes n'en démontrent l'indécidabilité).
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  16. #15
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    3e cas : d'autres dont on ne sait pas
    Ta question serais alors pouvons nous démontrer qu'une conjecture pourrait être indécidable ?

    Exemple conjecture de Goldbach ? "Si la conjecture de Golbach est indécidable, alors elle est vraie dans le modèle standard de l'arithmétique"

    Patrick

  17. #16
    ilelogique

    Re : indécidabilité de la décidabilité

    Non,rien sur votre lien qui répond à ma question,
    merci quand meme
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  18. #17
    ilelogique

    Re : indécidabilité de la décidabilité

    Re, non ma question n'est pas "pouvons nous démontrer qu'une conjecture pourrait être indécidable ? " car sinon, j'aurais sûrement écrit un truc comme ça :
    "pouvons nous démontrer qu'une conjecture pourrait être indécidable ? "
    Godel a lui meme trouvé des propositions dont il a prouvé l'indécidabilité, donc oui, nous savons que c'est possible.

    Je la remets encore :
    existe-t-il des énoncés dont on a prouvé que la décidabilité n'est pas décidable ?

    j'ai posé plus haut cette question sous plusieurs formes.

    En gros, pour essayer de vous suivre, oui :
    on peut se demander par exemple si pour tout énoncé est-on certain qu'on peut dire si il est décidable ou pas ?
    ou bien y a-t-il des énoncés pour lesquels on a prouvé qu'on ne pourrait pas (et donc indécidabilité de la décidabilité)
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  19. #18
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    on peut se demander par exemple si pour tout énoncé est-on certain qu'on peut dire si il est décidable ou pas ?
    ou bien y a-t-il des énoncés pour lesquels on a prouvé qu'on ne pourrait pas (et donc indécidabilité de la décidabilité)
    Dans toutes les logiques ?

    Patrick

  20. #19
    ilelogique

    Re : indécidabilité de la décidabilité

    je pose la question pour la logique classique à priori, mettons dans l'axiomatique de l'arithmétique, peu importe,je cherche à savoir si il existe des résultats de ce type
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  21. #20
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    je pose la question pour la logique classique à priori, mettons dans l'axiomatique de l'arithmétique, peu importe,je cherche à savoir si il existe des résultats de ce type :
    Donc cela concerne à priori la notion décidabilité dans le domaine de la logique classique du premier ordre.

    Citation Envoyé par ilelogique Voir le message
    Par exemple on ne sait toujours pas si la conjecture de Syracuse est décidable ou non dans l'arithmétique.
    Ma question est de savoir si on en sera forcément sûr un jour.

    C'est à dire, il y a des énoncés décidables, d'autres non et 3e cas : d'autres dont on ne sait pas
    ma question est de savoir si il existe un exemple d'énoncé dont on aurait démontré qu'on ne pourra jamais savoir si il est décidable ou pas.
    La notion de conjecture proposé par shokin me semblait être un bon élément pour essayer à vous suivre.

    Qu'elle différence alors entre "on ne sait pas" et on ne peut la démontrer ou démontrer sa négation dans le cadre d'une théorie du domaine de la logique classique ?

    Désolé mais j'ai toujours l'impression que votre énoncé est circulaire d’où effectivement une fuite à l'infini.

    Patrick
    Dernière modification par invite6754323456711 ; 15/07/2013 à 18h07.

  22. #21
    ilelogique

    Re : indécidabilité de la décidabilité

    quand je dis on ne sait pas, je parle de la décidabilité, pas de savoir si on peut ou non prouver l'énoncé lui même
    il faudrait médiat oui,
    je vous propose de relire ce que j'ai mis, car il me semble vraiment que vous ne comprenez pas, vous confondez des choses surement
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  23. #22
    Jiav

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    La question :
    existe-t-il des énoncés pour lesquels on a prouvé que la décidabilité est indécidable ???
    presque autrement dit : a-t-on prouvé que tout énoncé est soit décidable soit indécidable ? (ou bien cela dépend-il de la théorie, de la richesse du langage ?)
    Pour un énoncé quelconque indécidable dans une certaine axiomatique, il existe toujours une autre axiomatique dans laquelle il est décidable. Médiat vous le confirmera s'il passe par là et que ça lui chante. A+
    The opposite of a deep truth may well be another deep truth. Information is physical.

  24. #23
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message

    je vous propose de relire ce que j'ai mis, car il me semble vraiment que vous ne comprenez pas, vous confondez des choses surement
    Surement , car moi je pense que vous ne faite que re-énoncé avec vos mots le premier cas que j'ai souligné et donc du sophisme.

    Patrick

  25. #24
    ilelogique

    Re : indécidabilité de la décidabilité

    évidement qu'un énoncé indécidable peut etre décidable dans une autre théorie puisqu'il suffit de l'ajouter aux axiomes !
    c'est pas ce que je dis enfin ! et je ne tourne pas en rond !
    La conjecture de Syracuse est-elle décidable ou pas dans l'arithmétique ?
    Personne ne le sait.
    Mais en revanche on pourrait se demander si cette question : "la conjecture de Syracuse est-elle décidable dans l'arithmétique ?" est décidable ou non dans l'arithmétique (puisque la décidabilité peut s'y exprimer depuis Godel).
    C'est la décidabilité de la décidabilité, je ne vois pas où est le problème.
    je suis étonné que personne ne comprenne ce que je dis.
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  26. #25
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par Jiav Voir le message
    Pour un énoncé quelconque indécidable dans une certaine axiomatique, il existe toujours une autre axiomatique dans laquelle il est décidable. Médiat vous le confirmera s'il passe par là et que ça lui chante. A+
    Citation Envoyé par ù100fil Voir le message
    Bonsoir,

    Un exemple qui m'avait parler syntaxiquement et sémantiquement.

    Soit, en logique du premier ordre, F la formule close F = ∀x ∀y (p(x,y) → ∃ z ( p(x,z) ∧ p(z,y) ) P est un prédicat. Je n'ai que syntaxe, structure à base de symboles qui permet d’exprimer qq chose (signifiant). Pour la rendre sensible il nous faut lui donner du sens en proposant des interprétations (signifiés).

    En notant G l’implication, on a F :∀x ∀y ( G )

    - Interprétation I1 pour de domaine D1 qui est l'ensemble des réels. Le prédicat binaire p est l'ordre <

    si p(x,y) est faux, G est vraie
    si p(x,y) est vrai, alors x<y. Posons z =( x+y)/2. Alors, p( x,z) est vrai et p( z,y) aussi

    en conclusion, la formule F est satisfiable et I1 constitue un modèle pour F.

    - Interprétation I2 pour de domaine D2 qui est l'ensemble des entiers naturels. Le prédicat binaire p est encore l'ordre <

    si p(x,y) est faux, G est vraie
    si p(x,y) est vrai, alors x<y. Il n’existe pas d’entiers entre x et y dès lors que x et y sont consécutifs. G peut être fausse

    En conclusion F ne saurait donc être valide car il existe des interprétations qui ne satisfont pas F, mais elle n'est pas insatisfiable.

    Patrick
    Différence entre "vrai" et "valide"

    Citation Envoyé par Médiat Voir le message
    Bonsoir,

    Une autre façon de le dire : votre formule est indécidable dans la théorie des ordre totaux, alors qu'elle est un théorème dans la théorie des ordres denses.

    Patrick

  27. #26
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ù100fil Voir le message

    ...
    Patrick
    En logique classique, d'après le théorème de complétude, une proposition est indécidable dans une théorie s'il existe des modèles de la théorie où la proposition est fausse et des modèles où elle est vraie.

    Patrick

  28. #27
    ilelogique

    Re : indécidabilité de la décidabilité

    et ceci n'a rien à voir avec ma question, ou bien je ne pige plus rien !
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  29. #28
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    et ceci n'a rien à voir avec ma question, ou bien je ne pige plus rien !
    Je répondez à Jiav "être indécidable" est relatif à une théorie fixée.

    Tout comme vous faite systématiquement référence à la conjecture de Syracuse "affirmation péremptoire car non démontré". Ne pas réussir à démontrer un résultat conduit à ce poser la question est-ce indécidable ? Nous ne savons toujours pas si elle est indécidable, mais ce qui n'est pas non plus votre question.

    Patrick

  30. #29
    Jiav

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    évidement qu'un énoncé indécidable peut etre décidable dans une autre théorie puisqu'il suffit de l'ajouter aux axiomes !
    Tu trouves que c'est si trivial? Peut-être oui... comme toute chose une fois qu'on l'a comprise.

    Citation Envoyé par ilelogique Voir le message
    je suis étonné que personne ne comprenne ce que je dis.
    Ben, il me semble que j'ai répondu à ta question telle qu'elle était formulée initialement.

    Citation Envoyé par ilelogique Voir le message
    La conjecture de Syracuse est-elle décidable ou pas dans l'arithmétique ?
    Personne ne le sait.
    Mais en revanche on pourrait se demander si cette question : "la conjecture de Syracuse est-elle décidable dans l'arithmétique ?" est décidable ou non dans l'arithmétique (puisque la décidabilité peut s'y exprimer depuis Godel).
    C'est la décidabilité de la décidabilité, je ne vois pas où est le problème.
    Ok merci je comprend mieux ta question. Cela a un air trivial (si la conjecture n'est pas décidable dans l'arithmétique, alors sa décidabilité n'est pas non plus décidable), mais je ne suis pas certain de moi. J'ai un truc mais je repasserais
    Dernière modification par Jiav ; 15/07/2013 à 21h38.
    The opposite of a deep truth may well be another deep truth. Information is physical.

  31. #30
    ilelogique

    Re : indécidabilité de la décidabilité

    pour la première, oui, c'est trivial puisque tous les axiomes d'une théorie sont démontrés ipso-facto, si on rajoute l'énoncé dans la théorie, il devient un axiome et donc avec une démonstration de longueur 1.
    Pour la seconde pas d'accord, je ne vois pas pourquoi la décidabilité ne serait pas décidable si l'énoncé n'est pas décidable.
    Dans tous les cas, question comprise ou pas, je pense que personne ici n'a la réponse pour le moment,
    attendons Médiat alors... comment le colliciter ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

Page 1 sur 6 12 3 4 5 DernièreDernière

Discussions similaires

  1. Popper et indécidabilité
    Par Sylvestre dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 28/09/2012, 08h14
  2. indécidabilité et conjecture de Goldbach
    Par metacarambar dans le forum Mathématiques du supérieur
    Réponses: 62
    Dernier message: 12/04/2012, 17h54
  3. Indécidabilité (suite)
    Par danslideal dans le forum Mathématiques du supérieur
    Réponses: 13
    Dernier message: 20/12/2010, 17h36
  4. Décidabilité de la commutativité
    Par danslideal dans le forum Mathématiques du supérieur
    Réponses: 21
    Dernier message: 20/12/2010, 14h49