Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Page 1 sur 12 12 3 4 5 6 7 8 9 10 DernièreDernière
Affichage des résultats 1 à 15 sur 174

indécidabilité de la décidabilité

  1. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

    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
     


    • Publicité



  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 à 20h57.
     

  3. Paraboloide_Hyperbolique

    Date d'inscription
    juin 2012
    Localisation
    Liège
    Âge
    33
    Messages
    1 737

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

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

  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
     

  5. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

    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
     


    • Publicité



  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 à 11h23.
     

  7. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

    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
     

  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
     

  9. karlp

    Date d'inscription
    avril 2010
    Messages
    2 741

    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 )
     

  10. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

    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
     

  11. shokin

    Date d'inscription
    mars 2004
    Localisation
    Suisse
    Âge
    33
    Messages
    10 667

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

  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 à 17h48.
     

  13. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

    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
     

  14. shokin

    Date d'inscription
    mars 2004
    Localisation
    Suisse
    Âge
    33
    Messages
    10 667

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

  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
     


    • Publicité







Sur le même thème :





 

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, 09h14
  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, 18h54
  3. Indécidabilité (suite)
    Par danslideal dans le forum Mathématiques du supérieur
    Réponses: 13
    Dernier message: 20/12/2010, 18h36
  4. Décidabilité de la commutativité
    Par danslideal dans le forum Mathématiques du supérieur
    Réponses: 21
    Dernier message: 20/12/2010, 15h49