La méta-indécidabilité est-elle possible?

Il y a des problèmes qui sont décidables, il y en a qui sont indécidables, il y a la semi-décidabilité, etc.

Dans ce cas, je me demande si un problème peut être méta-indécidable. Cela signifie (du moins dans ma tête) que nous ne pouvons pas dire si c'est décidable ou non.

Peut-être qu'il est connu que la décidabilité est indécidable (tout est méta-indécidable) et qu'aucun algorithme n'existe pour prouver la décidabilité pour quoi que ce soit, donc la décidabilité doit être prouvée à la main au cas par cas.

Peut-être que ma question n'a pas de sens. Je suppose que nous sommes des machines au carbone exécutant des algorithmes très complexes et c'est pourquoi la question n'a de sens que dans ma tête.

Veuillez me faire savoir si la question doit être clarifiée. J'en aurai peut-être besoin moi-même en ce moment.

Je vous remercie.

Voici un rapide croquis pour montrer qu'il n'y a pas de machine de Turing pour décider si une classe arbitraire de problèmes est décidable.

Je devrais clarifier ce que j'entends par classe de problèmes: une classe de problèmes est une machine de Turing qui énumère les éléments (nombres naturels, par exemple) d'un ensemble récursivement énumérable l'un après l'autre, de sorte que chaque élément de l'ensemble est finalement imprimé . Le problème intuitivement saisi par T ( n ) est: "est le nombre n dans cet ensemble?". Cela capture les problèmes habituels dans le domaine de la calculabilité, tels que "est-ce que je suis l'indice d'une machine de Turing qui s'arrête sur une entrée vide?".$T$$T(n)$$n$

$M$$T$$\mathit{true}$$\mathit{false}$

$T$$T'$

1. $T$
2. $T$

$T$$M(T')$$\mathit{false}$

$T$$T'$$M(T')$$\mathit{true}$

$M(T')$$\mathit{true}$$T$$\mathit{false}$$M$$T$

Idée très cool!

Idée: Nous pouvons exploiter l'axiome de compréhension dans la théorie des ensembles ZF pour définir un langage qui dépend d'une déclaration indépendante.

Étape 1: Prenez votre déclaration préférée indépendante de ZF telle que AC - l'axiome de choix.

Étape 2: définir une langue L = {x dans {0,1} | x = 0 si AC et x = 1 si NOT AC}. Notez que L est soit {0} soit {1}. Maintenant, L est décidable, mais nous ne pouvons pas fournir avec certitude un programme qui décide L. Nous pouvons fournir le programme qui décide {0} ou nous pouvons fournir le programme qui décide {1}, mais nous ne savons pas avec certitude dont on décide L.

Étape 3: Utilisez cette idée pour définir un langage qui est décidable si AC et indécidable si PAS AC. Soit H l'ensemble d'arrêt qui est indécidable. Définissez L = {x | x est une chaîne si AC et x est dans H sinon NOT AC}. Si AC, alors L = l'ensemble de toutes les chaînes et L est décidable. Si ce n'est pas AC, alors L = H et L est indécidable. Que L soit décidable ou non est indépendant de ZF.