indécidabilité de la décidabilité

[ilelogique]

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

[invite6754323456711]

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

[Paraboloide_Hyperbolique]

Erreur, énoncé initial mal lu

[invite6754323456711]

Bonsoir

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

Patrick

[A voir en vidéo sur Futura]

[ilelogique]

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,

[invite6754323456711]

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

[ilelogique]

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.

[invite6754323456711]

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

[karlp]

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 )

[ilelogique]

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

[shokin]

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.

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 ?

[invite6754323456711]

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

[ilelogique]

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

[shokin]

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

[invite6754323456711]

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

[ilelogique]

Non,rien sur votre lien qui répond à ma question,
merci quand meme

[ilelogique]

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

[invite6754323456711]

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

[ilelogique]

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

[invite6754323456711]

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.

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

[ilelogique]

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

[invite73192618]

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+

[invite6754323456711]

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

[ilelogique]

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

[invite6754323456711]

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+

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

http://forums.futura-sciences.com/ep...ml#post4043251

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

[invite6754323456711]

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

[ilelogique]

et ceci n'a rien à voir avec ma question, ou bien je ne pige plus rien !

[invite6754323456711]

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

[invite73192618]

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

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.

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

[ilelogique]

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 ?