Ist Meta-Unentscheidbarkeit möglich?

Es gibt Probleme, die entscheidbar sind, es gibt einige, die nicht entscheidbar sind, es gibt Halbentscheidbarkeit usw.

In diesem Fall frage ich mich, ob ein Problem meta-unentscheidbar sein kann. Dies bedeutet (zumindest in meinem Kopf), dass wir nicht sagen können, ob es entscheidbar ist oder nicht.

Vielleicht ist bekannt, dass die Entscheidbarkeit unentscheidbar ist (alles ist meta-unentscheidbar), und es gibt keinen Algorithmus, der die Entscheidbarkeit für irgendetwas nachweist. Daher muss die Entscheidbarkeit von Fall zu Fall von Hand nachgewiesen werden.

Vielleicht macht meine Frage keinen Sinn. Vielleicht gehe ich davon aus, dass wir Kohlenstoffmaschinen sind, die sehr komplexe Algorithmen ausführen, und deshalb macht die Frage nur in meinem Kopf Sinn.

Bitte lassen Sie mich wissen, wenn die Frage weiterer Klärung bedarf. Ich kann das in diesem Moment selbst brauchen.

Vielen Dank.

Hier ist eine kurze Skizze, um zu zeigen, dass es keine Turing-Maschine gibt, um zu entscheiden, ob eine beliebige Klasse von Problemen entscheidbar ist.

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

Sehr coole Idee!

Idee: Wir können das Verständnisaxiom in der ZF-Mengenlehre nutzen, um eine Sprache zu definieren, die von einer unabhängigen Aussage abhängt.

Schritt 1: Nehmen Sie Ihre von ZF unabhängige Lieblingsaussage wie AC - das Axiom der Wahl.

Schritt 2: Definieren Sie eine Sprache L = {x in {0,1} | x = 0 wenn AC und x = 1 wenn NICHT AC}. Beachten Sie, dass L entweder {0} oder {1} ist. Nun ist L entscheidbar, aber wir können ein Programm, das über L entscheidet, nicht mit Sicherheit bereitstellen. Wir könnten das Programm bereitstellen, das über {0} entscheidet, oder wir könnten das Programm bereitstellen, das über {1} entscheidet, aber wir wissen es nicht mit Sicherheit welches man entscheidet L.

Schritt 3: Verwenden Sie diese Idee, um eine Sprache zu definieren, die bei Wechselstrom entscheidbar und bei NICHT Wechselstrom unentscheidbar ist. Sei H die Haltemenge, die unentscheidbar ist. Definiere L = {x | x ist eine Zeichenfolge, wenn AC und x in H, wenn NICHT AC}. Wenn AC, dann ist L = die Menge aller Zeichenfolgen und L ist entscheidbar. Wenn NICHT AC, dann ist L = H und L ist unentscheidbar. Ob L entscheidbar ist oder nicht, ist unabhängig von ZF.