TGI Hausaufgabe 7

# TGI Hausaufgabe 7 ##### Aufgabe 1 $L=\{\langle M\rangle\mid M\text{ ist Turingmaschine und }w\in L(M)\text{ genau dann, wenn }w\text{ Palindrom}\}$ Zeigen sie durch Reduktion, dass $L$ nicht Turing-entscheidbar ist. <details><summary>Überlegung</summary> 1.$L$ ist Co-Turing-erkennbar. 2.Wir können $\overline{A_{TM}}$ auf $L$ reduzieren. $\overline{A_{TM}}$ akzeptiert alle TM, die kein Wort akzeptieren. $L$ akzeptiert alle TM, die Eingaben nur akzeptieren, wenn sie Palindrome sind. $\to$ Man könnte sagen, füge zu $M$ die Palindrom-Akzeptanz hinzu. Aber was ist, wenn $M$ nur Palindrome akzeptiert? Sehe drunterstehenden Lösung. $\overline{A_{TM}}$ verwirft alle TM, die ein Wort akzeptieren. $L$ verwirft alle TM, die ein Nicht-Palindrom akzeptieren, oder ein Palindrome verwerfen. $\to$ Wenn $M$ ein Nicht-Palindrom akzeptiert funktioniert es, aber nicht, wenn $M$ bereits nur Palindrome akzeptierte. Man könnte vielleicht alle $w$, die $M$ akzeptiert, so verändern, dass $M$ stattdessen $ab$ akzeptiert. ==Ende== </details> Wir benutzen für die Reduktion auf $L$ das Problem $\overline{A_{TM}}$. Dieses ist nur Co-Turing-erkennbar und damit nicht Turing-entscheidbar. $\text{Turing-entscheidbar}<\overline{A_{TM}}\leqslant L$ Die Reduktionsfunktion $f:\{0,1\}^*\to\{0,1\}^*$ ist definiert als: $f(w)=\begin{cases}\langle M_{\langle M\rangle}\rangle&\text{, falls }w=\langle M\rangle\text{ gültige Kodierung einer Turingmaschine M ist}\\ \langle M_{ab}\rangle&\text{, sonst.} \end{cases}$ Dabei ist $M_{ab}$ eine Turingmaschine, die nur das Wort $ab$ akzeptiert. $M_{\langle M\rangle}=$ bei Eingabe $w$ arbeite wie folgt: 1. Füge zu jedem akzeptierenden Zustand in $M$, der nur durch Zeichen erreicht werden kann, die nicht das leere-Band-Zeichen sind, Transitionen und Zustände hinzu, so dass man mit $ab$ den akzeptierenden Zustand erreichen kann. 2. Simuliere $M$ über dem Band. 3. Akzeptiere, wenn $w$ ein Palindrom ist, oder wenn $M$ akzeptiert. 4. Sonst verwerfe die Eingabe. Sei $x\in\{0,1\}^*$, dann gilt: $x\in\overline{A_{TM}}\Longleftrightarrow x=\langle M\rangle\text{ und }M\text{ akzeptiert keine }w$ ==(Def. $\overline{A_{TM}}$)== $\Longleftrightarrow x=\langle M\rangle\text{ und }M_{\langle M\rangle}\text{ akzeptiert alle Palindrome und sonst keine weiteren }w$ ==(Def. $M_{\langle M\rangle}$)== $\Longleftrightarrow x=\langle M\rangle\text{ und }M_{\langle M\rangle}\text{ akzeptiert nur Palindrome}$ $\Longleftrightarrow f(x)\in L$ ==(Def. $L$)== Da $\overline{A_{TM}}$ nur Co-Turing-erkennbar ist, und wir $\overline{A_{TM}}$ auf $L$ reduzieren können, kann $L$ folglich höchstens Co-Turing-erkennbar, und damit nicht Turing-entscheidbar sein. ==Gibt es noch ein Problem, mit einer einfacheren Reduktion?== ##### Aufgabe 3 $\text{HAMCYCLE}=\{\langle G\rangle\mid G\text{ ist ein ungerichteter Graph mit einem hamiltonischen Kreis}\}$ Zeigen sie $\text{HAMCYCLE}\in NP$. Um zu zeigen, dass $\text{HAMCYCLE}\in NP$, geben wir einen Verifikator $V$ an, welcher das Problem in polynomineller Laufzeit verifiziert. $V=$ Bei Eingabe $x\in\{0,1\}^*$ arbeite wie folgt: 1. Verwerfe die Eingabe, falls $x$ keine gültige Kodierung eines ungerichteten Graphen mit zwei Knoten $s,t\in V$ und eines Weges, bestehend aus einer gleichen Anzahl Knoten und Kanten darstellt. 2. Prüfe, ob alle $v$ im Weg einem $v$ im Graphen entsprechen, und ob keine 2 sich gleichen. Falls nicht, verwerfe. Prüfe ebenfalls, ob alle Kanten einer Kante in $G$ entsprechen, und keine 2 sich gleichen. Prüfe auch, ob die Anzahl der Knoten im Weg, der in $G$ entspricht. Prüfe, ob der erste Knoten des Weges $s$ und der letzte $t$ entspricht. 3. Prüfe, ob für jedes $v_j$ im Weg es eine Kante $\{v_j,v_{j+1}\}$. Wenn nicht verwerfe. 4. Akzeptiere die Eingabe. Der Verifikator ist polynomiell, da das Überprüfen der Gültigkeit einer Kodierung nach Vorlesung polynomiell ist. Weiter ist auch das überprüfen der Vorkomniss, der Knoten&Kanten des Weges, in $G$ polynomiell. Weiterhin ist auch das überprüfen der Gleichheit der Anzahl von Knoten im Weg und in $g$, und das prüfen der Gleichheit der ersten und letzten Knoten mit $s$ und $t$ polynomiell. Zusätlich ist auch das Suchen einer passenden Kante für jedes $v_j$ und $v_{j+1}$ polynomiell. Damit ist $\text{HAMCYCLE}\in NP$, denn es gibt einen passenden Verifikator, der in polynomieller Zeit abläuft. ##### Aufgabe 4 Sei $\Sigma=\{a,b\}$ und $L=\{w\in\Sigma^*\mid |w|_b=3\}$. Geben sie einen DEA $A$ mit $L(A)=A$ an, und zeigen sie per Induktion für alle $w\in\Sigma^*$, dass $w\in L\Longleftrightarrow w\in L(A)$. Induktionsanfang: Sei $w=\varepsilon$, dann gilt: $\delta(q_0,\varepsilon)=q_0\notin F$ $\varepsilon$ ist ebenfalls nicht in $L$. Induktionsvoraussetzung: Sei $w\in\Sigma^*$, mit $|w|_b = k$. Falls $k>4$, dann gilt $\delta(q_0,w)=q_4\notin F$. Falls $k\leqslant 4$, dann gilt $\delta(q_0,w)=q_k$, wobei nur $q_3\in F$. Sei $w\in L$, dann gilt $|w|_b=3$. Damit gilt: $w\in L=w\in L(A)\Longleftrightarrow (|w|_b=3)=\delta(q_0,w)$ $\Longleftrightarrow l$