Kann eine Turing-Maschine (TM) entscheiden, ob das Stoppproblem für alle TMs gilt?

Auf dieser Site gibt es viele Varianten der Frage, ob TMs das Stoppproblem entscheiden können, ob für alle anderen TMs oder bestimmte Teilmengen. Diese Frage ist etwas anders.

Es wird gefragt, ob die Tatsache, dass das Stoppproblem für alle TMs gilt, von einem TM entschieden werden kann. Ich glaube, die Antwort ist nein und möchte meine Argumentation überprüfen.

1. Definieren Sie die Meta-Stopping-Sprache als die Sprache, die aus TMs besteht, die entscheiden, ob ein TM anhält.$L_{MH}$

2. $L_{MH}= \emptyset$ aufgrund des Stoppproblems.

Die lautet also genauer: Ist es entscheidbar, ob ?$L_{MH} = \emptyset$

3. Nach dem Satz von Rice ist es unentscheidbar, ob eine neue Sprache leer ist.
   In beiden Fällen ist es unentscheidbar, ob ist , wenn re ist oder nicht . L M H = $L_{MH}$$L_{MH} = \emptyset$

4. Daher ist es unentscheidbar, ob .$L_{MH} = \emptyset$

Dies beweist, dass ein TM nicht entscheiden kann, ob das Stoppproblem für alle TMs gilt.

Ist mein Verständnis richtig?

UPDATE: Ich versuche zu zeigen, dass ein TM das Stoppproblem nicht "beweisen" kann, wenn eine Definition von "beweisen" intuitiv korrekt erscheint. Unten sehen Sie, warum ich das für richtig halte.

Wir können ein TM erstellen , das auf folgende Weise erzeugt. Das TM nimmt ein Tupel . Es simuliert für Iterationen. Wenn alle Paare akzeptiert , die anhalten, und alle anderen ablehnt, akzeptiert . Andernfalls wird , wenn falsch entscheidet oder nicht anhält. L M H ( M i , M j , w k , s t e p s ) M i ( M j , w k ) s t e p s M i ( M j , w k ) M M H M i M i M $M_{MH}$$L_{MH}$$(M_i,M_j,w_k,steps)$$M_i(M_j, w_k)$$steps$$M_i$$(M_j, w_k)$$M_{MH}$$M_i$$M_i$$M_i$

M i M i M M H M i M $M_{MH}$ stoppt nicht, da es für jedes eine unendliche Anzahl von Paaren auswerten muss . Außerdem können alle nicht angehalten werden. kann kein akzeptieren oder ablehnen, da es aus der Simulation nicht weiß, dass alle nicht anhalten können. Somit ist die Sprache, die es definiert, nicht neu und nicht entscheidbar.$M_i$$M_i$$M_{MH}$$M_i$$M_i$

M M H M i M M H M i M M H M M $M_{MH}$ fängt meine Intuition darüber ein, was es meiner Meinung nach für ein TM bedeutet, das Halteproblem zu beweisen. Andere Vorschläge, wie , alle abzulehnen oder einen bekannten Beweis geben Vorwissen, dass das Stoppproblem für alle . Dies kann nicht als etwas beweist, da die Prämisse von die Schlussfolgerung ist, die es beweist, und daher zirkulär ist.$M_{MH}$$M_i$$M_{MH}$$M_i$$M_{MH}$$M_{MH}$

Ein anderer Gesichtspunkt: Sei eine Formalisierung der Aussage " L M H = ∅ " in ZFC ; (trivial) haben wir:$\varphi$$L_{MH} = \emptyset$

• die Menge ist entscheidbar;$P = \{ x \mid x \mbox{ is a valid proof of } \varphi \mbox{ in ZFC}\}$

• $M$$\varphi$$\neg \varphi$$M$

• $\{ M \mid M \mbox{ decides } P \}$

Die Sprache der Turing-Maschinen, die über das Stoppproblem entscheiden, ist entscheidend. Eine Turingmaschine, die entscheidet, gibt einfach immer NEIN aus.

$\emptyset$

$T$$L(T) = \emptyset$

Sie verstehen den Satz von Rice falsch.

Der Satz von Rice besagt in diesem Zusammenhang, dass Sie das Problem "Entscheidet T die leere Sprache?" Nicht entscheiden können.

Bei Ihrem Problem geht es nicht darum, zu entscheiden, ob eine beliebige Turing-Maschine die leere Sprache entscheidet. Ihr Problem ist, ob es ein M gibt oder nicht, das über die leere Sprache entscheidet.

Und solche M existieren. Sie können es sogar noch besser machen: Sie können tatsächlich ein solches M konstruieren und einen Beweis dafür liefern, dass es die leere Sprache entscheidet.

Das allgemeine Problem, dass es nicht entscheidbar ist, bedeutet nicht, dass Sie bestimmte Instanzen nicht lösen können. Tatsächlich gibt es mit der üblichen Methode, alle Beweise aufzulisten, eine Turingmaschine, die:

• Akzeptiert jede Turingmaschine, für die ein Beweis vorliegt, dass sie die leere Sprache entscheidet
• Lehnt jede Turingmaschine ab, für die ein Beweis vorliegt, dass sie die leere Sprache nicht entscheidet
• Hört nicht auf, wenn es nicht so oder so bewiesen werden kann.

Die Definition über Entscheidbarkeit aus Wikipedia :

Eine rekursive Sprache ist eine formale Sprache, für die es eine Turing-Maschine gibt, die, wenn sie mit einer endlichen Eingabezeichenfolge dargestellt wird , anhält und akzeptiert, wenn die Zeichenfolge in der Sprache vorliegt, und ansonsten anhält und ablehnt. Die Turing-Maschine hält immer an: Sie wird als Entscheider bezeichnet und soll die rekursive Sprache bestimmen.

Mit anderen Worten, es ist entscheidbar, ob es eine Turing-Maschine gibt, die alle Eingabezeichenfolgen entscheidet. Es ist unentscheidbar, ob für jede Turing-Maschine nicht alle Eingabezeichenfolgen festgelegt werden, was bedeutet, dass keine oder einige Zeichenfolgen festgelegt werden können, aber es gibt mindestens eine (aber praktisch mindestens unendlich viele), über die sie nicht entscheiden kann.

$L$$L = \emptyset$$L_{MH} = \emptyset$