Können wir zeigen, dass eine Sprache nicht rechnerisch aufzählbar ist, indem wir zeigen, dass es keinen Verifizierer dafür gibt?

11

Eine der Definitionen einer rechnerisch aufzählbaren Menge (ce, äquivalent zu rekursiv aufzählbar, äquivalent zu semidecidable) ist die folgende:

AΣ ist ce, wenn es eine entscheidbare Sprache (genannt Verifizierer) st für alle ,VΣxΣ

xA Wenn es ein st .yΣx,yV

Eine Möglichkeit zu zeigen, dass eine Sprache nicht ce ist, besteht darin, zu zeigen, dass es keinen entscheidbaren Prüfer dafür gibt. Ist diese Methode nützlich, um zu zeigen, dass Sprachen in der Praxis nicht ce sind?V

Anonym
quelle
3
Was ist ce (meintest du re?)
Ran G.
Ich kann mir keine Situation vorstellen, in der dies nützlich ist, um zu beweisen, dass eine Sprache nicht CE ist. Ich erwarte , dass Sie leicht ersetzen könnten mit in einer viel eine Reduktion. Wenn Sie sich eine andere Reduzierung einfallen lassen würden, würde ich erwarten, dass "negative Ausgänge" nicht viel bedeuten würden, da existenziell quantifiziert wird. A x , y V yVAx,yVy
Lucas Cook
@RanG., Re ist die alte Terminologie, heutzutage wird sie von Leuten, die in der Berechenbarkeitstheorie arbeiten, normalerweise als ce bezeichnet. (Wenn Sie über den Grund für die Änderung in der Terminologie interessiert sind, schlage ich vor, Robert Soares Homepage zu überprüfen.)
Kaveh
@ Kaveh danke. Jeden Tag lernt man neue Dinge ...
Ran G.

Antworten:

4

In der Praxis beweisen wir normalerweise nicht nur, dass eine Sprache neu ist oder nicht. Wenn die Sprache re ist, wollen wir wissen, ob sie rekursiv ist. Wenn es nicht re ist, wollen wir wissen, welche Art von Turing-Abschluss es hat, nicht nur, dass der Turing-Grad nicht re ist.

Wenn zum Beispiel ein Problem mit dann ist nicht re, aber diese Tatsache über den Turing-Sprung ist informativer als nur zu wissen, dass nicht re istPPT0PP

Während Sie also im Prinzip zeigen können, dass eine Sprache nicht neu ist, indem Sie beweisen, dass es keinen Prüfer gibt, ist es in der Praxis informativer zu beweisen, dass die Sprache nicht neu ist, indem Sie zeigen, dass sie etwas berechnet, das kein Satz berechnen kann. Die Art dieses "Etwas" gibt normalerweise nützliche Informationen über das untersuchte Problem.

Carl Mummert
quelle
3

Um die Terminologie klar zu machen, verwende ich: decidable = rekursiv = berechenbar, semidecidable = rekursiv aufzählbar = rechnerisch aufzählbar, co-semidecidable = co-rekursiv aufzählbar = co-rechnerisch aufzählbar.

In der Praxis besteht eine übliche Methode, um zu zeigen, dass eine Sprache nicht semidecidable ist, darin, zu zeigen, dass sie nicht entscheidbar ist und dass sie co-semidecidable ist. Sie nutzen dann die Tatsache, dass jede Sprache, die sowohl semidecidable als auch co-semidecidable ist, auch zu dem Schluss kommen kann, dass Ihre Sprache nicht semidecidable ist. (Beachten Sie, dass dies nur in eine Richtung funktioniert: Eine Sprache kann weder semidecidable noch co-semidecidable sein. In diesem Fall benötigen Sie eine andere Methode.)

Als Beispiel: Wir wissen, dass die Entscheidung, ob ein mehrdeutig ist , nicht zu entscheiden ist, aber es ist leicht, einen Co-Semidecide durchzuführen: Sie geben einfach eine Zeichenfolge mit zwei verschiedenen Parsen an. Dies impliziert, dass es nicht halbentscheidbar ist, ob ein mehrdeutig ist.CFGCFG

Eine andere Methode besteht darin, zu zeigen, dass die Sprache für eine höhere Ebene der arithmetischen Hierarchie vollständig ist .

Es ist natürlich möglich, direkt zu beweisen, dass es keinen Prüfer gibt, aber dies ist oft mühsam, da es normalerweise den Beweis wiederholt, dass das Stoppproblem unentscheidbar ist. Beachten Sie jedoch, dass das obige Argument im Wesentlichen implizit beweist, dass es keinen Verifizierer geben kann. Ich denke, Sie könnten sagen, dass es eine Methode ist, um zu beweisen, dass es keinen Verifizierer gibt, aber dann könnten Sie jeden Beweis der Nicht-Halbentscheidbarkeit als Beweis dafür betrachten, dass es einen gibt kein verfier.

Alex ten Brink
quelle
Es gibt einen Fehler in Ihrer Sprache. Eine Sprache kann nicht halbentscheidbar und nicht halbentscheidbar sein. Unentscheidbare Sprachen sind solche Sprachen.
Dave Clarke
@ DaveClarke: Ich habe einige Terminologiedefinitionen hinzugefügt. Ist es jetzt richtig?
Alex Ten Brink
Nicht ( halbentscheidbar ) nicht (entscheidbar) co-halbentscheidbar.
Dave Clarke
@ DaveClarke: Ich habe eine Notiz hinzugefügt, die besagt, dass es nur in eine Richtung funktioniert.
Alex Ten Brink
3
Ich bin nicht davon überzeugt, dass dies eine Technik ist, die jeder anwenden würde. Warum reduzieren Sie das Problem nicht auf ein bekanntes "nicht halbentscheidbares" Problem?
Dave Clarke