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



+ Répondre à la discussion
Page 2 sur 4 PremièrePremière 2 DernièreDernière
Affichage des résultats 16 à 30 sur 57

indécidabilité de la décidabilité

  1. ansset

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

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

    bjr, j'ai lu plusieurs articles sur les différences entre la décidabilité mathématique/algorithmique.
    en première lecture, j'ai l'impression que l'une s'intéresse aux énoncés et l'autre à la prise décision et à la théorie elle-même.
    la notion "d'arret" par exemple existe dans le second cas , pas dans le premier.
    en tout cas, tous s'accordent à distinguer les deux.
    je suis loin d'être assez informé pour avoir un avis argumenté, mais une démo partant d'un principe d'équivalence me semble douteux.

    -----

    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !
     


    • Publicité



  2. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 014

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

    Il y a me semble-t-il une confusion.
    On peut définir, disons en arithmétique pour préciser les choses, la démontrabilité, et aussi, comme vous le faites, la décidabilité d'un énoncé.
    Ce prédicat de décidabilité est il décidable ? (!!!), c'est à dire, si on se place dans le cadre de la théorie de Turing, existe-t-il un algorithme permettant de savoir à coup sur si un énoncé est décidable ou non ?
    Il n'y a aucune raison de l' affirmer: en fait la réponse est non ! ce n'est pas parce que le terme décidabilité contient le mot décidable qu'on pourrait en déduire la décidabilité de la décidabilité !
    Il n'est pire sot que qui ne veut pas comprendre .
     

  3. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

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

    Merci, donc :
    1) en admettant cette coïncidence ma preuve vous semble-t-elle correcte ?

    2) Pour la coïncidence, le théorème de complétude de Gödel affirme qu'un énoncé P qui est décidable dans une théorie T (donc vrai dans un modèle de T) si et seulement si il existe une suite finie d'énoncées partants de T qui, dans un système de déduction, prouve P (P est démontrable dans T) : or la correspondance de Curry-Howard ne permet-elle pas alors d'établir une correspondance bi-univoque entre les deux décidabilités ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  4. c.bien.moi

    Date d'inscription
    mars 2016
    Messages
    2

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

    Bonsoir,

    C'est dommage que tes questions soient restées sans réponse, pourtant il me semble qu'il y a des logiciens qui fréquentent ce forum...

    En même temps ta question est peut-être une question qui est encore sans réponse, je pense en particulier aux liens entre indécidabilité logique et calculatoire, il me semble improbable qu'aucun logicien n'ait réfléchie à cette question, il donc fort probable que tu t'appuis sur une conjecture qui reste à démontrer ou à infirmer.

    Bonne soirée.
     

  5. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

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

    Bonjour,
    je suis bien d'accord que c'est dommage qu'aucun logicien ne vienne répondre à mes questions, quand bien même serait-ce pour dire ici qu'ils n'ont pas les réponses.
    mais bon, ça viendra peut-être ?
    Merci.
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     


    • Publicité



  6. Matmat

    Date d'inscription
    mai 2005
    Messages
    1 037

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

    Tout ce que vous demandez c'est est ce qu'on peut faire la démonstration d'un résultat connu et déjà démontré en partant d'une hypothèse qu'on peut contester . Si la démonstration est correcte mais l'hypothèse contestable , il n'y a pas besoin de logicien .. Tout repose sur l'admission ou pas de l'hypothèse contestable .
     

  7. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

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

    Bonjour,
    si le résultat est connu et démontré en avez-vous une preuve logique svp ? Car je ne trouve rien là dessus (sur l'existence d'énoncés dont la décidabilité n'est pas décidable)
    Ensuite je suis d'accord que l'hypothèse que je prends doit être discutée (c'est pourquoi je fais appel au théorème de complétude puis à la correspondance de Cury-howard), pensez-vous par exemple qu'il serait judicieux que j'ouvre une nouvelle discussion à cet égard ?
    Enfin on peut aussi, il me semble, admettre temporairement cette hypothèse et voir si, en ce cas, ma preuve est valide ou non (c'est d'ailleurs ce que fait souvent la logique : on démontre des choses sous certaines hypothèses...) donc je veux bien savoir si ma preuve est correcte dès lors qu'on admet cette hypothèse (qui par ailleurs certes doit être discutée)
    Il me semble que tout mon propos ici fait bien appel à des logiciens car, et je ne vous cache pas que je m'en navre, depuis 2 pages d'échanges nous n'avons pour ainsi dire pas encore parlé de logique !!
    Merci.
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  8. Matmat

    Date d'inscription
    mai 2005
    Messages
    1 037

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

    Citation Envoyé par ilelogique Voir le message
    je ne trouve rien là dessus (sur l'existence d'énoncés dont la décidabilité n'est pas décidable).
    Mais plus haut on vous a cité le "problème de l’Arrêt" pourtant.
     

  9. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 014

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

    Il est vrai que j'ai répondu de façon peu formelle, préférant vous laisser réfléchir.
    Notons qu'une preuve faisant appel à une coïncidence n'en est pas une.
    Je précise la confusion que vous avez faite:
    "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"
    Le fait qu'une affirmation soit codable sous la forme d'un prédicat n'implique pas qu'elle soit codable sous la forme d'un algorithme terminant à coup sur. C'est précisément le principal enseignement des travaux de Gödel et Turing.
    Que vous faut-il de plus ?
    Je ne voulais pas vous aider plus qu'il ne me paraissait nécessaire et ai donc laissé un flou sur le terme "décidable" (je suis un peu comédien parfois).
    Je n'entrerait pas dans les détails mais je donnerai les indications suivantes:
    Décidable au sens de Gödel s'applique à des énoncés mathématique.
    La théorie de Gödel permet de construire des énoncés indécidables particuliers dans toute théorie mathématique consistante contenant l'arithmétique.
    Décidable au sens de Turing s'applique à des familles d'énoncés, par exemple du type la machine de Turing M s’arrête au bout d'un temps fini quand on la fait travailler sur la donnée n.
    La théorie de Turing permet de construire des familles d'énoncés dans lesquels on trouve une infinité d'indécidables, quelque soit la théorie permettant de définir la calculabilité dans laquelle on se place, par exemple en prenant pour M une machine universelle dans l'exemple ci-dessus.
    Il n'est pire sot que qui ne veut pas comprendre .
     

  10. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 014

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

    Bien sur, il fallait entendre théorie mathématique définie par un ensemble récursif d'axiomes ...
    Bref ce qu'on entend habituellement par théorie mathématique, dans laquelle la notion de démonstration est des plus claires.
    Il n'est pire sot que qui ne veut pas comprendre .
     

  11. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

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

    Matmat : je ne vois pas le rapport entre le problème de l'arrêt et le fait qu'il existe des énoncés dont la décidabilité n'est pas décidable.
    Schrodies-cat : je prétends que la formule Dec(A) est codable au sens de Gödel ici. je ne vois pas de quelle confusion vous parlez, entre quoi et quoi ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  12. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 014

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

    Je voulais illustrer les deux notions d'indécidabilité .Le théorème dont vous parlez est un autre théorème.
    En fait, pour vous donner une idée de sa démonstration, si la décidabilité était décidable, on pourrait construire une théorie complète, non contradictoire et à l'axiomatique récursive par l'algorithme suivant: en énumérant les énoncés de cette théorie, en testant un par un si ces énoncés sont décidables, et en ajoutant au fur et à mesure comme axiome chaque énoncé indécidable pour poursuivre.

    Votre confusion, je l'ai pointée précisément est sur "coder", ce n'est pas la même chose de coder comme prédicat et de coder comme algorithme.
    Dernière modification par Schrodies-cat ; 18/03/2016 à 12h18.
    Il n'est pire sot que qui ne veut pas comprendre .
     

  13. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

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

    De ce que je comprends de votre proposition c'est que vous ajoutez mon ensemble G à AP dans ma preuve, mais G n'est pas récursivement énumérable (sinon l'ensemble des énoncés décidables E serait récursif)
    Ensuite je ne vois pas trop où je confonds les codages, je parle de codages au sens de Gödel et ensuite (on y revient encore) j'admets que la décidabilité au sens de Gödel implique celle au sens de turing et je déduis l'existence de la machine de turing qui s'arrête pour toute formule A sur la décision de dec(A), les deux codages sont donc distincts non ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
     

  14. Schrodies-cat

    Date d'inscription
    avril 2015
    Messages
    1 014

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

    Oui, bon, je n'ai peut être pas lu avec suffisamment de soin votre lancement de ce sujet. Il semble que nous soyons assez d'accord sur ce que vous avez proposé, dont j'aurais en fait proposé dans mon dernier message une démonstration alternative, et peut être mieux formalisable.
    Il est vrai que pour ce genre de chose, il serait en principe nécessaire d'utiliser un formalisme rigoureux, mais cela rend souvent la compréhension laborieuse.
    J'enfoncerais cependant mon clou en répétant que habituellement, la décidabilité au sens de Gödel porte sur des énoncés particuliers et la décidabilité au sens de Turing porte sur des familles d'énoncés (on rencontre cela aussi dans la notion de "théorie décidable en logique mathématique".
    L'indécidabilité de Gödel est relative à une théorie donnée ; un énoncé pet être indécidable dans un théorie particulière mais décidable dans une théorie plus puissante (dans laquelle il restera bien entendu d'autres indécidables).
    Dans une famille d'énoncés indécidable au sens de Turing, quelle que soit la théorie (raisonnable) dans laquelle on se place, il restera des indécidables.
    On ne peut donc identifier les notions d'indécidables aux sens de Gödel et de Turing, même si ces deux notions sont profondément liées.
    Il n'est pire sot que qui ne veut pas comprendre .
     

  15. ilelogique

    Date d'inscription
    mai 2008
    Âge
    46
    Messages
    482

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

    re,
    Au sens de Gödel (avec le théorème de complétude) un énoncé P est indécidable dans une théorie T si il n'existe pas de démonstration de P ni de démonstration de NonP ou bien si il y a des modèles de T où P est vraie et d'autres modèles où P est fausse. un ensemble.
    or au sens de Turing un énoncé P est indécidable dans une théorie s'il n'existe aucune machine de Turing qui s'arrête pour dire si P est vrai ou non.
    Et donc il me semblait qu'avec Curry Howard on pouvait établir la correspondance.
    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, 21h38
  2. Popper et indécidabilité
    Par Sylvestre dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 28/09/2012, 09h14
  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