Wie kann man feststellen, ob eine Sprache erkennbar, miterkennbar oder entscheidbar ist?

8

Wenn Sie eine Sprache L haben, ohne Beweise zu machen, gibt es eine Möglichkeit zu erkennen, ob sie erkennbar oder miterkennbar oder entscheidbar ist?

Grundsätzlich alle Hinweise oder Tricks, die verwendet werden können, um zu erzählen. Oder vielleicht die gängigen Muster, nach denen gesucht werden muss, um festzustellen, um welche Art es sich handelt?

Omega
quelle
"ohne irgendwelche Beweise zu machen", ich kann dir irgendwie alles beweisen. (:
Ran G.
1
In der Mathematik wird ein "Trick" gewöhnlich als "Theorem" und manchmal als "Lemma" bezeichnet.
Andrej Bauer
Einige gebräuchliche Muster sind diejenigen, die im Satz von Rice (der eine unentscheidbare Menge beweist) und im Satz von Rice-Shapiro (der eine nicht erkennbare Menge beweist) angesprochen werden. Diese sind besonders hilfreich für das Muster "die Menge der (codierten) TMs so dass wir beim Ausführen von M dieses Verhalten beobachten"MM
Chi

Antworten:

6

L ist erkennbar

Eine Sprache erkennbar ist , wenn und nur wenn es einen Verifizierer für existiert L , wo ein Verifizierer eine Turing Maschine ist , dass stoppt an allen Eingängen und für alle w & Sigma; * , w L c & Sigma; * . V  nimmt  w , c . Im Allgemeinen wird c als "Zertifikat" oder "Beweis" angesehen, dass w in L ist, und der Prüfer V prüft, ob c ein gültiger Beweis dafür ist, dass w in L istLLwΣwLcΣ.V accepts w,ccwLVcwL. (Beachten Sie, dass diese Definition der Erkennungsdefinition entspricht, da wir einen Erkenner für eine Sprache aus einem Verifizierer für diese Sprache erstellen können.) Um festzustellen, ob eine Sprache in RE enthalten ist oder nicht, können wir die folgende Frage stellen:

Einen String gegeben , könnte man beweisen , dass w L ?wLwL

Betrachten wir zum Beispiel . H A L T ist erkennbar , weil Ihnen das beweisen M Aussetzer auf w , kann ich Ihnen nur sagen , die Anzahl der Schritte , die Sie ausführen sollten M für und wenn M halt tut nach , dass viele Schritte, würden Sie davon überzeugt , dass M , w H A L T .HALT={M,w | M is a TM that halts on w}HALTMwMMM,wHALT

L ist miterkennbar

In ähnlicher Weise eine Sprache ist Co-erkennbar , wenn und nur wenn ihr Komplement erkennbar ist, oder in anderen Worten , wenn ein Prüfer für existiert ˘ L . Um zu sehen, ob eine Sprache in Co-RE ist, können wir fragen:LL¯

Könnten Sie bei einer gegebenen Zeichenfolge beweisen, dass w L ist ?wLwL

Wenn wir noch einmal das Beispiel von , können wir diese Intuition verwenden, um zu zeigen, dass H A L T nicht miterkennbar ist. Dies liegt daran, dass ich Ihnen nichts sagen kann, um Sie davon zu überzeugen, wenn ich Ihnen sage, dass eine Maschine M bei Eingabe w nicht anhält. Ich könnte M auf w laufen lassen, aber selbst wenn wir M laufen gesehen haben und es noch nicht zum Stillstand gebracht haben, wissen wir nicht, dass es irgendwann in der Zukunft nicht mehr zum Stillstand kommen wird.HALTHALTMwMwM

L ist entscheidbar

Schließlich ist eine Sprache ist entscheidbar , wenn beide L und ¯ L erkennbar sind. Wenn also die Antwort auf die beiden oben genannten Fragen Ja lautet, ist die Sprache entscheidbar.LLL¯

Betrachten Sie als Beispiel . Könnte ich Ihnen bei einer gegebenen Zeichenfolge w L beweisen, dass w L ist ? Klar, ich könnte die Anzahl von a s und die Anzahl von b s hochzählen und zeigen, dass sie gleich sind, also ist L erkennbar. Was ist, wenn w L ? Ich könnte beweisen, dass ein String nicht in L ist, indem ich zeige, dass er entweder nicht die Form a n b m hat oder dass die Anzahl von nicht übereinstimmtL={anbn | nN}wLwLabLwLLanbm s und b s. Somit ist L miterkennbar. Da es sowohl erkennbar alsauch miterkennbar ist, ist L auch entscheidbar.abLL

Referenz: Ich bin ein TA für einen Kurs in Intro-Berechenbarkeits- / Komplexitätstheorie an meiner Universität und mein Professor hat diesen wirklich hilfreichen animierten Leitfaden erstellt, um über reguläre, entscheidbare und erkennbare Sprachen nachzudenken.

Roctothorpe
quelle
Danke für diesen Link! und danke an deinen prof dafür! es war großartig
nichtig
2

Hauptideen

Erkennbar zu sein bedeutet, dass Sie einen automatischen Prozess erstellen können (wir werden später darauf zurückkommen), der ein Wort als solchen Parameter verwendet

  • Wenn der automatische Prozess endet, wird entweder JA oder NEIN zurückgegeben.
  • Dieser automatische Prozess muss nicht bei jeder Eingabe beendet werden, sondern muss beendet werden, wenn das Eingabewort in der Sprache vorliegt.

wΣ,wLL

Entscheidbar zu sein bedeutet, dass Sie einen automatischen Prozess erstellen können, der ein Wort als Eingabe verwendet, so dass

  • Der automatische Vorgang endet immer
  • Es antwortet mit JA oder NEIN. Wenn es mit JA antwortet, ist das Wort in der Sprache, wenn es mit NEIN antwortet, ist das Wort nicht in der Sprache.

LL


Die Idee, um dieses Ergebnis zu beweisen, besteht darin, dass Sie einen automatischen Prozess aus den Prozessen aufbauen können, die Sie durch Erkennbarkeit und Co-Erkennbarkeit erhalten, indem Sie die Schritte beider Prozesse abwechseln, bis einer von ihnen die Antwort JA gibt. Einer von ihnen muss dies tun, da jedes Wort entweder in der Sprache ist oder nicht).


Automatische Prozesse

Ohne zu formal zu sein, wurden viele Maschinentypen entworfen, und im Grunde wurden alle mit Sprachtypen verknüpft (diese Typen hängen von den Werkzeugen ab, die zum Definieren solcher Sprachen erforderlich sind. Weitere Informationen finden Sie in der Chomsky-Hierarchie ).

Die übliche Bedeutung des automatischen Prozesses in Bezug auf die Entscheidbarkeit ist eine Turingmaschine. Sie können eine Turingmaschine so definieren, dass sie:

  • Empfangen Sie Werte von der Eingabe
  • Werte speichern
  • Lesen Sie die gespeicherten Werte
  • Berechnen Sie grundlegende mathematische Operationen für Werte
  • Testen Sie die grundlegenden mathematischen Eigenschaften dieser Werte und handeln Sie entsprechend, um schließlich eine Schleife zu erstellen.

Grundsätzlich kann eine Turing-Maschine alles tun, was Sie in einem Programm definieren können, außer es ist ein mathematisches Objekt mit unendlichem Speicher und Zeit für eine Berechnung. Es endet nicht immer.

MwMw


Lassen Sie uns nur darauf hinweisen, dass reguläre Sprachen - die (fast) die einfachste Art von Sprache sind, die Sie aus mathematischer Sicht vorstellen können - die eigentümliche Eigenschaft haben, dass sie unter Komplement geschlossen werden. Dies bedeutet im Wesentlichen, dass in diesen Sprachen die Begriffe Erkennbarkeit und Entscheidbarkeit gleichwertig sind. Dies gilt nicht, wenn Sie in der Chomsky-Hierarchie aufsteigen.


Beispiel einer unentscheidbaren Sprache

MwMw

MwM

Um zusammenzufassen

Bei einer bestimmten Sprache können Sie nicht einfach angeben, ob dies entscheidbar ist oder nicht. Es gibt keinen Algorithmus, der dies kann, und der Nachweis, dass eine Sprache nicht entscheidbar ist, erfordert einige Überlegungen und erfordert einige Kenntnisse über Turingmaschinen, diagonale Argumente usw.

Hier ist jedoch meine persönliche Art, mit dieser Frage umzugehen. Wenn ich eine Sprache lerne, gehe ich normalerweise davon aus, dass sie entscheidbar ist, es sei denn, sie enthält einen Hinweis auf die Funktionsweise von Turing Machine. In diesem Fall fange ich an, vorsichtig zu sein, und versuche, einen Algorithmus zu definieren, der die Sprache bestimmt. Wenn dies nicht einfach aussieht, ist es manchmal hilfreich, die Arbeit in einen Erkennungs- und einen Miterkennungsalgorithmus aufzuteilen. Wenn ich es immer noch nicht kann, würde ich versuchen, eine Verbindung zwischen dieser und einer anderen unentscheidbaren Sprache herzustellen, z. B. "Wenn ich diese Sprache entscheiden kann, kann ich das Stoppproblem entscheiden". Dies ist eine Turing-Reduktion auf ein unentscheidbares Problem, daher kann das erste Problem nicht entschieden werden. Wenn all dies fehlschlägt, kann ich versuchen, diagonale Argumente zu verwenden, aber dies kann etwas schwierig sein.

Wazdra
quelle
1

Ein Trick ist, dass wenn die Sprache endlich ist, Sie sicher wissen, dass sie entscheidbar ist - da Sie eine Maschine "fest codieren" können, um alles in dieser Sprache zu akzeptieren. Ich finde es jedoch am einfachsten, einfach aus einer anderen Sprache zu reduzieren

Steven
quelle
Gleiches gilt für co-finite Sprachen.
Raphael
Darüber hinaus ist eine Sprache mit einem endlichen Lösungsraum aufgrund ihrer Eingabe entscheidbar, da Sie eine Brute-Force-Suche durchführen können.
Jmite
1

Wie ich oben in meinem Kommentar erwähnt habe, finde ich es hilfreich, über den Lösungsraum des Problems nachzudenken.

SAT

Überlegen Sie jetzt, wann der Lösungsraum zählbar unendlich ist und wir jede mögliche Lösung nacheinander generieren können und das Testen jeder Lösung entscheidbar ist. In diesem Fall wissen wir, dass das Problem erkennbar ist. Zum Beispiel ist ein Problem mit der Frage "Gibt es eine natürliche Zahl, so dass ..." erkennbar, da wir bei 0 beginnen und jede Zahl nacheinander versuchen können. Wenn es eine Lösung gibt, werden wir sie garantiert finden, aber es gibt nicht unbedingt eine Grenze für die Zeit, die benötigt wird, um sie zu finden. Außerdem würde dieser Algorithmus niemals anhalten, wenn keine solche Ganzzahl vorhanden wäre, sodass er nicht beweist, dass ein Problem entscheidbar ist.

Sie können dieselbe Technik auf die Menge aller Zeichenfolgen, aller Ganzzahlen, aller Diagramme oder jeder endlichen Struktur anwenden, die wir aufzählen können. Dies würde nicht funktionieren, um eine reelle Zahl oder einen (möglicherweise unendlichen) Satz von Zeichenfolgen zu finden.

Beachten Sie jedoch, dass einige Probleme möglicherweise unendlich viele Lösungsräume haben und dennoch entscheidbar sind.

jmite
quelle
"Wenn der Lösungsraum zählbar unendlich ist, wissen wir, dass das Problem erkennbar ist." -- Nicht unbedingt. Erstens ist der Lösungsraum möglicherweise nicht effektiv aufzählbar (Beispiel: "Gibt es ein TM, das eine Gesamtfunktion berechnet und damit [nicht triviales Prädikat]?"). Zweitens kann die Entscheidung, ob das betrachtete Objekt eine Lösung ist, selbst unentscheidbar sein (Beispiel: "Finden Sie ein TM, das bei 77 nicht anhält.").
Raphael
NP{L| L Decidable}
Auch: "Alles mit einer endlichen" Menge von Möglichkeiten "zu versuchen, wird entscheidbar sein" - nein. Das Problem des Anhaltens hat zwei mögliche Antworten, ist aber unentscheidbar.
Raphael
@Steven Ja, aber das ist ein noch schwierigerer Beweis. (Die Menge, auf die Sie sich beziehen, wird normalerweise mit R bezeichnet, der Menge rekursiver (leicht entscheidbarer) Sprachen.)
Raphael
Ich denke, ich sollte das klarstellen. Die Idee ist, dass Sie das Halteproblem nicht so brutal erzwingen können, wie Sie es beispielsweise mit 3-SAT tun können. Oder wie Sie, wenn Sie etwas auf einem PDA ausführen, alle möglichen Pfade ausprobieren können, obwohl dies nicht deterministisch ist. Bei einem TM ist dies jedoch nicht möglich, da es unendlich lange dauern kann. Daher ist die Menge der zu versuchenden Dinge, dh die möglichen Pfade durch das Programm, nicht begrenzt.
Jmite
0

Der Trick, um festzustellen, ob eine Sprache unentscheidbar ist, besteht darin, sich die Frage zu stellen: "Kann ich eine Berechnung der Turing-Maschine mit dieser Sprache codieren?" Oder allgemeiner: "Wird es so kompliziert wie das, was bei einer Berechnung passiert?". Natürlich ist diese Codierung manchmal schwierig, und es hilft, eine Liste unentscheidbarer Probleme zu kennen, auf die man sich reduzieren kann (wie das Problem der Post-Korrespondenz). Wenn Sie eine solche Reduzierung nicht finden, denken Sie an Algorithmen, um Ihre Sprache zu bestimmen. Zum Beispiel ist die Sprache von Listen mit ganzen Zahlen in aufsteigender Reihenfolge nicht endlich, aber es ist einfach, einen Algorithmus zu entwerfen, der prüft, ob eine Liste in aufsteigender Reihenfolge sortiert ist, sodass diese Sprache entscheidbar ist. Und für viele Sprachen wissen wir nichts über ihre Entscheidbarkeit, daher ist dies eine schwierige Frage.

Denis
quelle
Diese Antwort fördert die falsche Intuition, siehe hier .
Raphael
Ich stimme nicht zu, dass es eine falsche Intuition ist. Natürlich habe ich nicht alle Themen erwähnt, zum Beispiel kann die Sprache wie in Ihrem Beispiel übermäßig kompliziert dargestellt werden, und deshalb muss man sie zuerst vereinfachen, um zu ihrem "Wesen" zu gelangen. Ich habe auch nicht erwähnt, dass es unentscheidbare Sprachen gibt, die über dem Anhalten und unter dem Anhalten liegen, weil ich nicht denke, dass dies der Intuition auf dieser Ebene hilft.
Denis