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



+ Répondre à la discussion
Page 1 sur 4 12 3 DernièreDernière
Affichage des résultats 1 à 15 sur 57

indécidabilité de la décidabilité

  1. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    470

    indécidabilité de la décidabilité

    Bonjour,
    je voudrais savoir ce que vous pensez du raisonnement suivant et, donc, de la validité de l'assertion suivante :
    "Dans toute théorie suffisamment élaborée (par exemple contenant l'arithmétique de Peano) : il existe un énoncé dont la décidabilité n'est pas décidable".

    Je viens douter ici de la validité de mon propos notamment parce que j'y suppose la coïncidence entre les décidabilités aux sens de Gödel et de Turing (quid de cette coïncidence ?)
    Au demeurant, il me semble que Giuseppe Longo en a proposé une démonstration.

    Et donc :
    Nous savons grâce à Gödel que pour tout énoncé A de l'arithmétique (notée AP) il existe un prédicat Théo(A) qui code le fait que A soit un théorème de AP (on peut coder «*théo(A)=il existe une preuve Y de A*») donc le prédicat «*Dec(A)=théo(A) ou théo(nonA)*» est un prédicat affirmant que A est décidable dans AP, il devrait être codable aussi. Or si on appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables dans AP alors E étant récursivement énumérable mais non récursif, on a G qui n'est pas récursivement énumérable (sinon E serait récursif), donc si pour toute formule A on a Dec(A) qui est dans E alors, si la décidabilité au sens de Gödel implique celle au sens de Turing (ce qu'on peut raisonnablement croire...), il existe un algorithme (une machine de Turing) qui s'arrête à coup sûr et décide pour chaque formule A de la validité de Dec(A), si bien qu'on saurait pour toute formule A si elle est décidable ou non, ce qui est contradictoire avec le fait que E soit non récursif, donc on déduit qu'il existe une formule A telle que Dec(A) est dans G, c'est-à-dire l'existence d'une formule dont la décidabilité n'est pas décidable.

    Ceci impliquerait bien sûr qu'il y aurait une formule dont la décidabilité de la décidabilité ne serait pas décidable et donc l'existence, par induction, d'une chaîne infinie…

    Qu'en pensez-vous svp ?
    merci.

    -----

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


    • Publicité



  2. ansset

    Date d'inscription
    novembre 2009
    Localisation
    Fresnes
    Âge
    57
    Messages
    23 262

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

    Citation Envoyé par ilelogique Voir le message
    Ceci impliquerait bien sûr qu'il y aurait une formule dont la décidabilité de la décidabilité ne serait pas décidable et donc l'existence, par induction, d'une chaîne infinie…

    Qu'en pensez-vous svp ?
    merci.
    moi j'en pense que ça sent bon la verdure.
    Cdt
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
     

  3. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    470

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

    Ah bon ?
    Et pouvez-vous me dire où ça ne va pas alors svp merci ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  4. ansset

    Date d'inscription
    novembre 2009
    Localisation
    Fresnes
    Âge
    57
    Messages
    23 262

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

    je ne suis pas spécialiste de ces questions, mais deux points me sautent aux yeux.
    une analogie ( même plus ) entre la notion de "décidabilité" logique (Godel ) et celle algorithmique (Turing ).
    tu sembles prendre la seconde pour "retourner" la première.

    sur le second point je suis moins sur, mais je pense que mettre Dec(A) ( en reprenant tes termes ) dans E , est un abus de logique. ( celle mathématique ).
    d'où ton laius sur la récursivité, qui semble prendre appui sur la logique algorithmique pour faire dire à la logique mathématique ce qu'elle ne dit pas.

    en attendant un logicien....
    afin qu'il me corrige ou me complète.
    Cdt
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
     

  5. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    470

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

    Bonjour,
    la coïncidence entre les deux décidabilité j'en ai parlé plus haut
    Sinon un "abus de logique" dont vous parlez je ne sais pas ce que c'est. En revanche dec(A) est un prédicat, il a donc vocation à aller dans E il me semble.
    Aussi : le laïus sur la récursivité me parait logique, rien de mal là dedans : si dec(A) est indécidable on peut bien concevoir de faire le même raisonnement sur des formules du type dec(nondec(B)) je ne vois pas ce qui vous chiffonne.
    Enfin, c'est quoi la verdure svp ?
    merci.
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     


    • Publicité



  6. ansset

    Date d'inscription
    novembre 2009
    Localisation
    Fresnes
    Âge
    57
    Messages
    23 262

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

    un prédicat n'est pas un énoncé décidable.
    la verdure se mange ou parfois est utilisée en infusion , voir se fume aussi.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
     

  7. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    470

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

    dec(A) est un énoncé, il peut donc être décidable ou pas
    je n'ai pas fumé...
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  8. Deedee81

    Date d'inscription
    octobre 2007
    Localisation
    Courcelles - Belgique
    Âge
    55
    Messages
    27 438

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

    Salut,

    Citation Envoyé par ilelogique Voir le message
    je n'ai pas fumé...
    Inutile de le préciser. C'était du second degré
    Tout est relatif, et cela seul est absolu. (Auguste Comte)
     

  9. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    470

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

    J'espère qu'un logicien va répondre car je voudrais bien être sûr de ma preuve
    merci
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  10. Matmat

    Date d'inscription
    mai 2005
    Messages
    1 035

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

    D'accord mais c'est un peu donner le bâton pour se faire battre d'utiliser " la coïncidence entre les décidabilités aux sens de Gödel et de Turing " alors qu'un argument diagonal doit faire l'affaire.
     

  11. gandhalf.legris

    Date d'inscription
    octobre 2015
    Messages
    373

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

    Citation Envoyé par ilelogique Voir le message
    J'espère qu'un logicien va répondre car je voudrais bien être sûr de ma preuve
    merci
    bonjour ,
    j'apprécie beaucoup votre pseudo mais je trouve qu'un e est en trop
    c'est comme si je demandais pouvez vous dire qu'un état d'un objet est vrai tout en étant faux sans utiliser la physique quantique ( superposition d'état à écarter ... ) .
    certains répondraient , tu veux quelle couleur pour les matelas ...
     

  12. illusionoflogic

    Date d'inscription
    janvier 2015
    Localisation
    non
    Messages
    1 116

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

    C'est pour moi la différence entre arithmétique et algèbre ; l'un à donner l'algorithme et l'autre la logique. (je précise que ce sont des domaines fils, des ramifications).
    Lisez mes propos. Je suis pas là.
     

  13. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    470

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

    je ne vois pas quel argument diagonal peut venir remplacer l'appel à cette coïncidence,
    aussi première question :
    - en supposant cette coïncidence ma preuve est-elle correcte ?
    - Quid de cette coïncidence ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  14. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    470

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

    Re bonjour,
    je réponds d'abord à vos assertions qui, selon moi, ne sont pas en lien avec mon sujet :
    - L'île logique est le nom de ma compagnie de théâtre burlesque et sciences théoriques, c'est bien sûr un jeu de mot, si bien que le "e" est indispensable.
    - pour la couleur des matelas et le vrai et faux quantique ou pas dont vous parlez : no comment, aucun lien avec ma question (ou tout du moins non argumenté)
    - Pour arithmétique et algèbre, notons que la construction de celles-ci, depuis au moins le XXe siècle, reposent toutes sur la logique, algorithmique comprise, et encore une fois, je ne vois pas le lien avec ma question.

    Aussi, s'il vous plaît, si vous souhaitez commenter ce que je viens de dire et/ou dire à nouveau des choses hors sujet, merci d'ouvrir une autre discussion (à laquelle je me ferai un plaisir de me joindre !)

    Et donc, revenons à mes moutons svp, je remets ici ma double question, je suis ici pour une question de logique :

    1) peut-on raisonnablement supposer l'équivalence entre la décidabilité au sens de Gödel et celle au sens de Turing ? Et surtout : si non, quel argument logique l'infirme ?
    2) Et c'est le but PRINCIPAL de ma question : en admettant l'équivalence entre les deux décidabilités, la démonstration suivante du fait qu'il existe des énoncés dont la décidabilité n'est pas décidable vous paraît-elle bonne ? Et si non : quel argument avancez-vous ?

    Merci.

    Nous savons grâce à Gödel que pour tout énoncé A de l'arithmétique (notée AP) il existe un prédicat Théo(A) qui code le fait que A soit un théorème de AP (on peut coder «*théo(A)=il existe une preuve Y de A*») donc le prédicat «*Dec(A)=théo(A) ou théo(nonA)*» est un prédicat affirmant que A est décidable dans AP, il devrait être codable aussi. Or si on appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables dans AP alors E étant récursivement énumérable mais non récursif, on a G qui n'est pas récursivement énumérable (sinon E serait récursif), donc si pour toute formule A on a Dec(A) qui est dans E alors, si la décidabilité au sens de Gödel implique celle au sens de Turing (ce qu'on peut raisonnablement croire...), il existe un algorithme (une machine de Turing) qui s'arrête à coup sûr et décide pour chaque formule A de la validité de Dec(A), si bien qu'on saurait pour toute formule A si elle est décidable ou non, ce qui est contradictoire avec le fait que E soit non récursif, donc on déduit qu'il existe une formule A telle que Dec(A) est dans G, c'est-à-dire l'existence d'une formule dont la décidabilité n'est pas décidable.

    Ceci impliquerait bien sûr qu'il y aurait une formule dont la décidabilité de la décidabilité ne serait pas décidable et donc l'existence, par induction, d'une chaîne infinie…
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  15. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    470

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

    j'oubliais, évidemment : je suis tout à fait preneur d'un autre argument dans ma preuve qui, du coup, éviterait de faire appel à cette "coïncidence" qui, semble-t-il, ne fait pas consensus....
    merci
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     


    • Publicité







Sur le même thème :





 

Discussions similaires

  1. indécidabilité de la décidabilité
    Par ilelogique dans le forum Epistémologie et Logique
    Réponses: 173
    Dernier message: 21/09/2017, 20h38
  2. Popper et indécidabilité
    Par Sylvestre dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 28/09/2012, 08h14
  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