Unentscheidbares Problem und seine Verneinung ist unentscheidbar

Viele "berühmte" unentscheidbare Probleme sind dennoch zumindest halbentscheidbar, und ihre Ergänzung ist unentscheidbar. Ein Beispiel kann vor allem das Stopp-Problem und seine Ergänzung sein.

Kann mir jemand ein Beispiel geben, in dem sowohl ein Problem als auch seine Ergänzung unentscheidbar und nicht halbentscheidbar sind? Ich habe über die Diagonalisierungssprache Ld nachgedacht, aber es scheint mir nicht, dass die Ergänzung unentscheidbar ist.

Bedeutet dies in diesem Fall, dass eine Turing-Maschine M einige Zeichenfolgen "verlieren" kann, die stattdessen erkannt werden sollten, da sie Teil der Sprache sind, die wir identifizieren möchten?

Betrachten Sie die folgende Sprache:

$$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$

ist unentscheidbar und nicht halbentscheidbar, und dasselbe gilt für sein Komplement. Warum? Die Intuition ist, dass " M 2 bei Eingabe x 2 nicht anhält" nicht halbentscheidbar ist, so dass L 2 nicht halbentscheidbar ist; und wenn Sie das Komplement von L 2 betrachten , passiert dasselbe für M 1 . Dies kann durch Reduzierungen genauer formalisiert werden.$L_2$$M_2$$x_2$$L_2$$L_2$$M_1$

Allgemeiner gesagt, wenn eine Sprache ist, die unentscheidbar und nicht halbentscheidbar ist, dann$L$

$$L' = \{(x,y) : x \in L, y \notin L\}$$

erfüllt Ihre Anforderungen: ist unentscheidbar und nicht halbentscheidbar, und dasselbe gilt für das Komplement von L ' .$L'$$L'$

Beachten Sie, dass die überwiegende Mehrheit der Probleme das gesuchte Kriterium erfüllt: Sowohl das Problem als auch seine Ergänzung sind nicht halbentscheidbar. Dies liegt daran, dass es nur unzählige teilentscheidbare Probleme gibt, aber es gibt unzählige Probleme.

Ein Beispiel läßt das Halteproblem für Turingmaschinen und sei M die Klasse von Turing - Maschinen mit einem Orakel für seine  H . Lassen Sie H 2 das Halteproblem für seinen  M . Ich beanspruche , dass weder H 2 noch  ¯ H 2 ist semi-entscheidbar$H$$\cal{M}$$H$$H_2$$\cal{M}$$H_2$$\overline{H_2}$

Wir können zeigen, dass von keiner Maschine in  M entschieden wird : Das Argument ist dasselbe wie das Argument, dass das Problem des Anhaltens  einer gewöhnlichen Turingmaschine H von keiner gewöhnlichen Turingmaschine entschieden wird. Nehmen wir nun zum Widerspruch an, dass H 2  von einer gewöhnlichen Turing-Maschine T halb entschieden wird  . Nun, mit einem Orakel für  H können wir testen, ob T  für eine bestimmte Eingabe anhält, was der Tatsache widerspricht, dass keine Maschine in  M H 2 entscheidet  . So H 2  ist nicht semi-entscheidbar.$H_2$$\cal{M}$$H$$H_2$$T$$H$$T$$\cal{M}$$H_2$$H_2$

Es bleibt zu zeigen , daß nicht semi-entscheidbar ist. Beachten Sie zunächst, dass es von einer Maschine in M halb entschieden wird  : Auch hier ist das Argument dasselbe wie das von H  , das von einer gewöhnlichen Turing-Maschine halb entschieden wird. ¯ H 2  kann von keiner Maschine in  M halbentschieden werden, da H 2 und  ¯ H 2 ansonsten von Maschinen in M halbentschieden würden  , sodass beide Sprachen von Maschinen in  M bestimmt würden . Wir wissen aber bereits, dass H 2  von keiner Maschine in  M entschieden wird . Deshalb,$\overline{H_2}$$\cal{M}$$H$$\overline{H_2}$$\cal{M}$$H_2$$\overline{H_2}$$\cal{M}$$\cal{M}$$H_2$$\cal{M}$  wird von keiner Maschine in M vorentschieden. Ferner ¯ H 2 ist nicht halb entschieden durch jede gewöhnliche Turing Maschine, daM jede gewöhnliche Turing Maschine enthält. (Eine gewöhnliche Turingmaschine ist eine Turingmaschine mit einem Orakel für H, die dieses Orakel niemals benutzt.)$\overline{H_2}$$\cal{M}$$\overline{H_2}$$\cal{M}$$H$

Hier sind einige natürliche Beispiele:

• Die Sprache aller Turing-Maschinen, die bei allen Eingaben anhalten, wird manchmal als TOT bezeichnet. Diese Sprache ist -vollständig.$\Pi_2^0$

• Die Sprache aller Turing-Maschinen, die bei unendlich vielen Eingaben anhalten, wird manchmal als INF bezeichnet. Diese Sprache ist auch -vollständig.$\Pi_2^0$

• Die Sprache aller Turing-Maschinen, die bei willkürlich langen Eingaben anhalten, wird manchmal als COF bezeichnet. Diese Sprache ist -vollständig.$\Sigma_3^0$

und Σ 0 3 sind Ebenen derarithmetischen Hierarchie. Aus der Vollständigkeit ergibt sich insbesondere, dass diese Sprachen weder teilentscheidbar noch teilentscheidbar sind.$\Pi_2^0$$\Sigma_3^0$