Unentscheidbares Problem und seine Verneinung ist unentscheidbar

13

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?

Giulia Frascaria
quelle

Antworten:

15

Betrachten Sie die folgende Sprache:

L2={(M1,x1,M2,x2):M1 halts on input x1 and M2 doesn't halt on input x2}.

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.L2M2x2L2L2M1

Allgemeiner gesagt, wenn eine Sprache ist, die unentscheidbar und nicht halbentscheidbar ist, dannL

L={(x,y):xL,yL}

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

DW
quelle
7

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-entscheidbarHMHH2MH2H2¯

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.H2MHH2THTMH2H2

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,H2¯MHH2¯MH2H2¯MMH2M  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.)H2¯MH2¯MH

David Richerby
quelle
7

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.Π20

  • Die Sprache aller Turing-Maschinen, die bei unendlich vielen Eingaben anhalten, wird manchmal als INF bezeichnet. Diese Sprache ist auch -vollständig.Π20

  • Die Sprache aller Turing-Maschinen, die bei willkürlich langen Eingaben anhalten, wird manchmal als COF bezeichnet. Diese Sprache ist -vollständig.Σ30

und Σ 0 3 sind Ebenen derarithmetischen Hierarchie. Aus der Vollständigkeit ergibt sich insbesondere, dass diese Sprachen weder teilentscheidbar noch teilentscheidbar sind.Π20Σ30

Yuval Filmus
quelle