Kann eine Turing-Maschine die Sprache

Lassen Gibt es eine Turingmaschine R, die die Sprache L ∅ entscheidet (ich meine nicht erkennt) ?

Es scheint, dass dieselbe Technik, die verwendet wurde, um zu zeigen, dass hier funktionieren sollte.$\{A \mid A \text{ is a DFA and } L(A)=\emptyset\}$

Mit Markieren meinen Sie wahrscheinlich die Erreichbarkeitsanalyse - die Suche nach einem Pfad vom Ausgangszustand zum akzeptierenden Zustand. In der Tat ist die Sprache eines DFA leer, wenn es keinen solchen Pfad gibt.

Beginnen wir mit einem Beispiel, warum dies in TMs fehlschlägt. Stellen Sie sich ein TM vor, das in seine Eingabe ignoriert, aber a auf sein Band schreibt , den Kopf nach rechts bewegt und in den Zustand q 1 wechselt. In q 1 ignoriert es erneut die Eingabe, schreibt a , bewegt den Kopf nach links und geht bis q 2 . In q 2 , wenn er liest ein , dann schreibt es ein , bewegt sich der Kopf nach rechts und geht zurück auf q 1 .$q_0$$a$$q_1$$q_1$$a$$q_2$$q_2$$a$$a$$q_1$

Das heißt, die Maschine schreibt nur $a$ und wechselt zwischen zwei Zuständen ( und q 2 ) und hat immer zwei benachbarte a auf dem Band.$q_1$$q_2$$a$

Wir fügen nun einen Übergang von , der beim Lesen von b in einen akzeptierenden Zustand übergeht und anhält.$q_2$$b$

Die Sprache dieser Maschine ist leer. In der Tat bleibt der Lauf immer in der -Schleife stecken und wird niemals in den akzeptierenden Zustand gelangen. Es gibt jedoch einen staatlichen Weg zu einem akzeptierenden Staat. Also, was ist schief gelaufen?$q_1-q_2$

Nun, intuitiv ist der "Zustand" eines TM nicht informativ genug, um die Fortsetzung des Laufs zu beschreiben. Um alle Informationen zu erhalten, benötigen Sie die Konfiguration des TM, die den Status, die Position des Kopfes und den Inhalt des Bandes enthält. Wenn Sie einen Konfigurationspfad (der als Ausführen bezeichnet wird ) zu einer akzeptierenden Konfiguration finden, ist die Sprache tatsächlich nicht leer und es handelt sich um eine iff-Bedingung.

Das Problem bei der Verwendung der Erreichbarkeitsanalyse im Konfigurationsdiagramm besteht darin, dass sie möglicherweise unendlich ist. Deshalb ist die Entscheidung über die Leere der Sprache unentscheidbar.

Dies ist auch der Grund, warum die Nichtleere der Sprache erkennbar ist. Sie können ein BFS für das Diagramm mit der unendlichen Konfiguration durchführen. Wenn es einen Weg zu einem akzeptierenden Zustand gibt, werden Sie ihn schließlich finden. Wenn dies jedoch nicht der Fall ist, können Sie bei einer unendlichen Suche stecken bleiben.

ist aufgrund desSatzesvonRiceunentscheidbar, der besagt, dass nicht triviale Eigenschaften von Teilfunktionen nicht entscheidbar sind.$A$

1. Es gibt ein TM, das keine Zeichenfolge akzeptiert. (Was direkt in den Ablehnungszustand geht).
2. Es gibt ein TM, das jede Zeichenfolge akzeptiert. (Was direkt in den Akzeptanzzustand geht).

Dies bedeutet, dass die von Elementen von berechneten Funktionen eine nicht triviale Eigenschaft haben. Daher ist A nicht entscheidbar.$A$$A$

nur unter der Annahme entschieden werden, dass DFAs auf spezielle Weise wie Zustandsübergangstabelle usw. codiert sind (wir können aufgrund des Satzes von Rice nicht entscheiden, ob ein TM nur reguläre Sprachen akzeptiert!). In diesem Fall ist der Satz von Rice nicht anwendbar, da die bestimmte Codierung eines Elements erforderlich ist, um über E zu entscheiden. Wir entscheiden uns also nicht nur für Teilfunktionen.$E$$E$

(Das heißt, wenn das Problem wäre, zu entscheiden, ob ein bestimmtes TM ein DFA - oder ein DFA-berechenbares - ist und die von ihm akzeptierte Sprache leer ist, wäre durch den Satz von Rice unentscheidbar. Beachten Sie, dass in diesem Fall A = E ist .)$E$$A = E$

Ein weiterer Hinweis: Versuchen Sie, das Halteproblem auf reduzieren .$L_\emptyset$

(Der ursprüngliche Hinweis ist, den Satz von Rice zu verwenden, aber in diesem Fall ist ein direkter Beweis auch ziemlich einfach.)

Lemma 1 : Wenn L unentscheidbar ist, ist auch das Komplement von L.

Wir wissen, dass das Halteproblem $H_{TM}$ unentscheidbar ist. Daher ist gemäß Lemma 1- Komplement des Stoppproblems auch $H_{TM}^c$ unentscheidbar.

$H_{TM}$ =$\{\langle M, x \rangle { }\mid \text{ M is a TM and M halts on input x } \}$

$H_{TM}^c$ =$\{\langle M, x \rangle { }\mid \text{ M is a TM and M loops on input x } \}$

$E_{TM}$ =$\{\langle M \rangle { }\mid \text{ M is a TM and L(M) = } \emptyset \}$

Angenommen, $E_{TM}$ ist entscheidbar. Wir werden $H_{TM}^c$ auf $E_{TM}$ reduzieren - mit anderen Worten, wir werden zeigen, wie man eine Turingmaschine $M_{H_{TM}^c}$ konstruiert , die $H_{TM}^c$ Verwendung des TM entscheidet, $M_{E_{TM}}$ , das $E_{TM}$ . Dies gibt uns einen Widerspruch, weil wir wissen, dass $H_{TM}^c$ unentscheidbar ist, und so $M_{H_{TM}^c}$kann nicht existieren. Das Wort „reduzieren“ bedeutet einfach, ein bestimmtes Problem zu lösen, indem es in ein anderes Problem umgewandelt wird, dessen Lösung wir bereits kennen. Die Turingmaschine für $H_{TM}^c$ kann also wie folgt aufgebaut sein:

$M_{H_{TM}^c}$ = „on Eingang$\langle M,x \rangle$

$\qquad$1. Konstruieren Sie den Code für ein TM, $M_1$ , das Folgendes ausführt:

$\qquad$ $\quad$ $M_1$ = "am Eingang$w$

$\qquad$ $\quad$1. Simulieren Sie $M$ auf $x$ .

$\qquad$ $\quad$2. Akzeptiere, wenn $M$ anhält. "

$\qquad$2. Führen $M_{E_{TM}}$ auf $\langle M_1 \rangle$

$\qquad$3. Akzeptieren Sie, wenn $M_{E_{TM}}$ akzeptiert, lehnen Sie etwas anderes ab. "

Es ist wichtig zu verstehen, dass das TM $M_1$ niemals tatsächlich simuliert wird - eine solche Simulation könnte in eine Endlosschleife gehen. Wir konstruieren lediglich den Code für $M_1$ .

$M_1$ ist so aufgebaut, dass es bei jeder Eingabe$w$$M$ mit der Eingabe$x$ simuliert. $M$ kann auf$x$ anhalten oder eine Schleife bilden,und daher kann es zwei Fälle geben:

$\quad$ 1. $M_1$ accepts all inputs $w$ if $M$ halts on $x$. $M_{E_{TM}}$ will reject $M_1$ as $L(M_1) \neq \emptyset$.

$\quad$ 2. If $M$ loops on $x$, $M_1$ will also loop for every input $w$ given to it. Anyway, as $M_{E_{TM}}$ is a $\quad$decider it will reject and halt on input $M_1$ as $L(M_1) = \emptyset$.

$Correctness$: Since $M_{E_{TM}}$ always halts (by our assumption), $M_{H_{TM}^c}$ also always halts. $M_{H_{TM}^c}$ accepts if $M_{E_{TM}}$ accepts, that is if $L(M_1) = \emptyset$ which happens if $M$ loops on $x$.
$M_{H_{TM}^c}$ rejects if $M_{E_{TM}}$ rejects that is $L(M_1) \neq \emptyset$ which happens if $M$ halts on $x$. Thus, $M_{H_{TM}^c}$ decides $H_{TM}^c$ which is a contradiction as $H_{TM}^c$ is undecidable.

$Nb:$

Let R be the reduction from $H_{TM}^c$ to $E_{TM}$.

The reduction gives:

i) $\langle M, x \rangle \in H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \in E_{TM}$

$\qquad$ M loops on input x iff the language recognised by $R(\langle M,x \rangle)$ accepts nothing

ii) $\langle M, x \rangle \notin H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \notin E_{TM}$

$\qquad$ M halts on input x iff the language recognised by $R(\langle M,x \rangle)$ accepts something

Proof by contradicting $A_{TM}= \{\langle M,w\rangle \mid M \text{ is a Turing Machine which accepts w}\}$, (which we know is undecidable).

Assume the existence of $R_{TM}$, a TM that decides $L_\emptyset$

Use can then use $R_{TM}$ in the construction of a TM $S_{TM}$, which is a decider for $A_{TM}$

$S_{TM}=^{definition}$ "On input $\langle M,w\rangle$, where $M$ is the encoding of a TM and $w$ is a string:

1. Modify $M$, taking into account the input $w$, such that the new $M$ (call it $M_1$) rejects all input which is not equal to $w$, where $w$ is built into its description. If the input is equal to $w$, then $M_{1}$ runs $M$ on $w$ and outputs whatever $M$ outputs.

2. Run $R_{TM}$ with the input $\langle M_1,w\rangle$

3. Output the opposite of $R_{TM}$s output."

The assumption that there exists a Turing Machine deicer for $L_\emptyset$, allows us to construct a decider for $A_{TM}$, which is a contradiction.

E={ | M is a TM and L(M)=Φ}. Is E Turing-recognizable?

E is a language, to accept language E we construct a Turing Machine. Suppose we create a Turing EM for the language E.

EM will be provided as input the encoding of another Turing machines, If that inputted machine M accepts an empty language then it will be a member of language E, else it will be not a member of language.

Suppose we have a Turing Machine M, we need to check if it accepts an empty language. Turing Machine EM have M and strings eps, a, b, aa, bb, ..... EM will check if M can reach a final state for at least on a single input, and if it accepts at least a single input it will be discarded and not included in language E. Now, see a possibility T.M M gets into a loop so M will keep on running and we couldn't decide whether it can accept or can't accept anything. Hence, this given language E is NOT RE.

PS: I think the complement of this given Language E will be RE.