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?

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$$L$$w \in \Sigma^*$$w \in L \leftrightarrow \exists c \in \Sigma^*. V\text{ accepts }\langle w, c\rangle$$c$$w$$L$$V$$c$$w$$L$. (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 ?$w \in L$$w \in L$

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 = \{\langle M, w\rangle\ |\ M\text{ is a TM that halts on }w\}$$HALT$$M$$w$$M$$M$$\langle M, w\rangle \in HALT$

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:$L$$\overline{L}$

Könnten Sie bei einer gegebenen Zeichenfolge beweisen, dass w ∉ L ist ?$w \not\in L$$w \not\in L$

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.$HALT$$HALT$$M$$w$$M$$w$$M$

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.$L$$L$$\overline{L}$

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 übereinstimmt$L = \{a^nb^n\ |\ n \in \mathbb{N}\}$$w \in L$$w \in L$$a$$b$$L$$w \not\in L$$L$$a^nb^m$ s und b s. Somit ist L miterkennbar. Da es sowohl erkennbar alsauch miterkennbar ist, ist L auch entscheidbar.$a$$b$$L$$L$

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.

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\in \Sigma^*, w\not\in L}$$L$

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.

$L$$L$

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.

$M$$w$$M$$w$

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

$M$$w$$M$$w$

$M$$w$$M$

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.

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

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.

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.