TGI Hausaufgabe 6

# TGI Hausaufgabe 6 ##### Aufgabe 1 Geben sie für die folgenden Sprachen(Mengen) die Erkennbar-/Entscheidbarkeit und die Abzählbarkeit an. a) Die leere Menge: Turing-entscheidbar, abzählbar b) Menge von Buchstaben * eine natürliche Zahl: Turing-entscheidbar, abzählbar c) Menge von Bruchzahlen zwischen 0 und ~0,7: Turing-entscheidbar, nicht abzählbar d) Nicht unbedingt Turing-erkennbare Turingmaschinen, die mind. eins von 0, 101, 110 akzeptieren: Nicht Turing-erkennbar oder Co-Turing-erkennbar, nicht abzählbar e) Turing-Maschinen, die bei der Eingabe $\varepsilon$ in $\leqslant77$ Eingaben terminieren: Turing-entscheidbar, nicht abzählbar f) Turing-Maschinen, die eine Eingabe $v$ haben, bei der sie in $|v|$ Schritten terminieren: Turing-Erkennbar, nicht abzählbar ##### Aufgabe 2 L ist Turing-Entscheidbar. Halt ist Turing-Erkennbar. a) Die Reduktionsfunktion ist nicht berechenbar, da sie nicht für alle Eingaben terminiert. Die linke Sprache hat keine Co-Turing-Entscheidbarkeit, damit sind die Eigenschaften der Rechten keine Teilmenge derer der Linken. b) Bei Falschen $w$ wird für $f(w)$ in $HALT$ stets Wahr zurückgegeben, obwohl es Falsch sein sollte. Das liegt daran, dass in der Reduktionsfunktion-Turingmaschine bei falschen Eingaben verworfen wird. von $HALT$ wird aber jede Verwerfung zu Wahr gemacht. Stattdessen sollte die Reduktions-Turingmaschine bei falschen Eingaben eine unendliche Berechnung starten. Das würde dann von $HALT$ zu Falsch gemacht werden. c) Man kann in Schritt 3 von $M_{<M>}$ nicht sagen Hält $M$ nicht, dann halte an. Das funktioniert nicht. Die Eigenschaften der Rechten Sprache müssen eine Teilmenge derer der linken sein. Das ist nicht der Fall, da nur die linke Sprache Co-Turing-Erkennbarkeit hat und nur die Rechte Turing-Erkennbarkeit. ##### Aufgabe 3 $HALT_{TM}^{\Sigma^*}$ ist **Turing-erkennbar**, aber nicht Co-Turing-erkennbar. $CO-EMPTY$ ist **nicht** Turing-erkennbar und **nicht** Co-Turing-erkennbar. $EVEN$ ist **Turing-erkennbar**, aber nicht Co-Turing-erkennbar. Gesucht ist $L_1$: $\text{Turing-entscheidbar}>|L_1|_{\text{Eigenschaften}}\geqslant|HALT|_{\text{Eigenschaften}}$ a) Wir nehemen für die Reduktion das Problem $HALT_{TM}^{\varepsilon}$. Dieses ist Turing-erkennbar. Die Reduktionsfunktion $f$ tut folgendes für die Eingabe $M\in\{0,1\}$: Falls $M$ keine gültige Turingmaschine ist, geben wir eine Turingmaschine $T$ zurück, die niemals terminiert. Sonst nehmen wir die gültige Turingmaschine $M$ und geben sie so modifiziert zurück, dass sie sich für jede mögliche Eingabe genauso verhält, wie sie sich für die Eingabe $\varepsilon$ verhält. Da $HALT_{TM}^{\varepsilon}$ nur Turing-erkennbar ist, und wir $HALT_{TM}^{\varepsilon}$ auf $HALT_{TM}^{\Sigma^*}$ reduziert haben, kann $HALT_{TM}^{\Sigma^*}$ folglich nicht Turing-entscheidbar sein: $\text{Turing-entscheidbar}<|HALT_{TM}^{\varepsilon}|_{\text{Eigenschaften}}\leqslant|HALT_{TM}^{\Sigma^*}|_{\text{Eigenschaften}}$ b) Wir nehmen für die Reduktion das Problem $A_{TM}$. Dieses ist weder Turing-erkennbar, noch Co-Turing-erkennbar. Die Reduktionsfunktion $f$ nimmt die Eingabe $<M,w>\in\{0,1,a,b\}$. Falls $<M,w>$ keine gültiges Turingmaschine-Wort-Paar ist, dann werden 2 Turingmaschinen zurückgegeben, die beide eine leere Sprache haben. Sonst wird einmal die Sprache $M$ in unveränderter Form zurückgegeben, und einmal eine Turingmaschine, mit einer Sprache, die nur das Wort $w$ akzeptiert, und dabei terminiert. Damit kann $CO-EMPTY_{TM}$ nicht Turing-entscheidbar sein. $\text{Turing-entscheidbar}<|A_{TM}|_{\text{Eigenschaften}}\leqslant|CO-EMPTY_{TM}|_{\text{Eigenschaften}}$ c) Wir nehmen für die Transition das Problem $HALT_{TM}^{\varepsilon}$, welches Turing-Erkennbar ist. Die Reduktionsfunktion $f$ nimmt die Eingabe $M\in\{0,1\}$. Falls $M$ keine gültige Turingmaschine ist, dann geben wir eine Turingmaschine zurück, die jede Eingabe nach einem Schritt verwirft, und das leere Wort $\varepsilon$. Sonst geben wir die Maschine $M$ so verändert zurück, dass alle Reject-Zustände zu Accept-Zuständen werden, und dass für jeden Schritt ein zusätzlicher Schritt hinzugefügt wird, der nichts verändert, und den man erst ausführen muss, bevor man weiter machen kann. Zusätlich geben wir das Wort $\varepsilon$ zurück. Damit kann $EVEN_{TM}$ nicht Turing-entscheidbar sein. $\text{Turing-entscheidbar}<|HALT_{TM}^{\varepsilon}|_{\text{Eigenschaften}}\leqslant|EVEN_{TM}|_{\text{Eigenschaften}}$