Le problème de savoir si un problème est indécidable...

[invite05799208]

...est-il décidable ou non ? (Du moins, si cette question est décidable... )
La question est là ! Merci pour vos réponses, si vous en avez.

(Médiat, je vous attends )
-----

[Médiat]

Bonjour,

Pour parler d'indécidabilité, il faut une théorie et une proposition formelle, je ne vois ni l'une ni l'autre dans votre question .

Maintenant, si on fait un peu de méta-mathématique, une proposition p indécidable dans une théorie T, en logique du premier ordre, cela veut dire qu'il existe des modèles de T U {p}, et des modèles de T U {non p}, je ne vois pas comment on peut modifier cet état de fait sans changer la logique utilisée (on ne peut toucher ni à T ni à p car sinon on change la question), et alors votre question devient : une proposition indécidable dans une théorie T pour une certaine logique, peut-elle être décidable dans une autre logique, et alors la réponse est triviale : oui (avec une logique sans aucune règle d'inférence, on ne peut pas démontrer grand chose) !

[invite05799208]

Merci pour votre rapide réponse !
Effectivement, je me rends compte que sans préciser de théorie ma question paraît quelque peu sans objet
Cela dit, à ce niveau-là, il est intéressant de noter que le problème de l'arrêt n'est pas défini dans une théorie purement formelle (pas de théorie axiomatique). Il repose uniquement sur la notion de programme, qui est, il me semble, assez claire et univoque pour que le problème le soit aussi.
En fait, arrêtez-moi si je me trompe, mais on peut voir les programmes comme des théories mathématiques axiomatiques, et voir le fait qu'un programme s'arrête ou non comme celui qu'il démontre ou non une proposition. On peut donc reformuler l'inexistence du programme de l'arrêt en disant : "Il existe des théories axiomatiques telles qu'il existe des énoncés dont on ne peut pas prouver si elles les démontrent ou non."
Ce serait donc une version faible du théorème de Gödel (mais là, je digresse ).
Quoi qu'il en soit, ne pourrait-on pas s'interroger sur l'existence d'un système formel (une sorte de méta-théorie) dans lequel on pourrait formaliser les théories, et dire si leurs questions sont décidables ou non... ?

[invite05799208]

On dirait que mon sujet ne passionne pas les foules

[A voir en vidéo sur Futura]