date-created: 2024-06-11 12:25:30 date-modified: 2024-09-24 04:35:51

Reduktionen

anchored to 112.00_anchor_overview proceeds from 112.16_nicht_erkennbar_entscheidbar Tags: #computerscience #complexitytheory

Wir wollen uns ferner die Ergebnisse von 112.16_nicht_erkennbar_entscheidbar nochmal anschauen:

Es muss viele Sprachen außerhalb des Raumes $RE$ geben!

Dabei haben wir eine Sprache $D$ konstruiert, die nicht spezifisch benannt/gelistet werden kann. Wir wussten ferner, dass sie nicht teil von $RE$ ist!

WDHL | Komplement einer Sprache

112.01_Sprachen

[!Definition]

Sei $L$ eine Sprache über $\Sigma$. Die Komplementsprache $L^c$ oder auch $\overline{L}$ ist definiert durch: #card $$L^C:=\{w\in {\Sigma }^{\ast }\mid w\notin L\}$$

Visuell etwa:

Es lässt sich jetzt eine Aussage über Komplementsprachen treffen:

Komplementsprachen entscheidbarer Sprachen sind entscheidbar

[!Satz]

Wir sagen, dass $L\in R⟺L^c\in R$ Also:

Eine Sprache ist Turing-entscheidbar genau dann, wenn ihr Komplement Turing-entscheidbar ist.

Wie würden wir das beweisen, was müssen wir konstruieren? (Turingmaschine!) #card

Wir beweisen das, indem wir eine Turingmaschine $M$ definieren.

Sei $M$ eine TM, die $L$ entscheiden kann - das heißt wir können etwa einen Aufzähler konstruieren, der klar entscheiden kann, ob ein Wort $\in L$ ist oder nicht!

Ferner definieren wir jetzt die “komplementierende Turingmaschine” $M_C$ als TM, die $M$ genau vertauscht. Also, wenn $M$ akzeptiert, dann verwirft $M_C$ ( wir invertieren damit die Ausgabe vollends!) Es folgt dann : $$\begin{array}{rlr}>w\in L& ⟹M\text{ akzeptiert }w& ⟹M_C\text{ verwirft }w⟹w\notin L(M_c)\\ >w\notin L& ⟹M\text{ verwirft }w& ⟹M_C\text{ akzeptiert }w⟹w\in L(M_c)>\end{array}$$

Und ferner können wir die Rückrichtung genauso beweisen!

Spannender wird diese Betrachtung, wenn wir schauen, ob man diese Struktur, bzw. Aussage auch für die Menge von erkennbaren Sprachen - oder allen anderen Sprachen, die nicht zwingend entscheidbar sind - bilden kann ( also wir wollen die obige Aussage für alle möglichen Sprachen umsetzen).

Wir definieren dafür jetzt: CoRE

coRE | complement-RE

Wir definieren diese Menge folgend:

[!Definition]

Die Menge $coRE$i st definiert durch $$coRE:=\{L\mid L^c\in RE\}$$

Was sagt uns diese Mengenbeschreibung? Ferner was lässt sich über das Verhältnis zwischen $RE,coRE,R$ sagen? #card

Eine Sprache liegt in der Menge, wenn ihr Komplement rekursiv aufzählbar ist!

(hier kann dann auch noch die Möglichkeit passieren, dass die TM nicht anhält, weil wir ja rekursiv aufzählbar einbeziehen!, aber das ist zu vernachlässigen) –> Wir wollen gleich noch herausfinden, wie genau diese beiden Mengen in Beziehung stehen, werden dabei herausfinden, dass der Schnitt dieser beiden Beschreibungen genau $R$ ist!

Daraus resultiert eine neue Frage:

Wie verhalten sich $RE$ und $coRE$ zueinander?!

mögliche Betrachtung könnten also sein:

Wir wollen jetzt evaluieren, welcher der obigen Darstellungen dafür passt.

Wir wissen schon, dass $R\in RE$ liegt und alle Komplemente von $R$ ebenfalls entscheidbar sind. Damit wissen wir, dass sie definitiv nicht disjunkt sind!

Entscheidbare Sprachen sind in $RE$ und in $coRE$:

[!Definition]

Wir sagen, dass $L\in R⟹L\in RE\cap coRE$

wieso folgt das, warum können wir das aussagen? #card

Wir wollen diese Aussage beidseitig beweisen:

$L\in R⟹L\in RE$ ist klar, da wir wissen, dass $R\subseteq RE$ Wir haben aber auch bewiesen, dass Komplementsprachen entscheidbarer Sprachen sind entscheidbar

Ferner wissen wir also, dass $R\in RE\cap coRE$ liegt!

Ferner werden wir zeigen, dass dieser Schnitt genau alle regulären Sprachen beschreibt!

R = $RE\cap coRE$

Obig haben wir gesehen, dass $R$ im Schnitt liegen muss.

Gibt es Sprachen noch weitere Sprachen in $(RE\cap coRE)\setminus R$?

NEIN

[!Satz]

Wir wollen zeigen, dass $R=RE\cap coRE$ ist! Wir behaupten also, dass $L\in R⟺L\in RE\wedge L\in coRE$

Wie können wir das am besten beweisen? Was ist die Idee / der Ansatz? #card

Idee: man kann eine TM konstruieren, die schaut, ob es in RE oder coRE steht –> sie ist also rekursiv aufzählbar, aber ferner auch ihr Komplement.

Wir bauen also eine TM für $L$ ($M$) und ihr Komplement für $L_C$ = $M_C$. Wir konstruieren nun eine weitere TM $\hat{M}$ welche folgende Operation durchläuft / beschreibt:

• Lasse $M$ und $M_c$ parallel auf der Eingabe $w$ laufen ( etwa über eine Zweiband-TM)
• Falls $M$ akzeptiert, dann soll auch $\hat{M}$ akzeptieren
• Falls $M_c$ akzeptiert, dann soll $\hat{M}$ verwerfen.

Was wir dann daraus folgern können: $$\begin{array}{rlrl}>w\in L& ⟹M\text{ akzeptiert}& & ⟹\hat{M}\text{ akzeptiert}\\ >w\notin L& ⟹w\in L_C& ⟹M_{c}akzeptiert& ⟹\hat{M}\text{ verwirft}>\end{array}$$

Eine Sprache ist also Turing entscheidbar, wenn sowohl sie selbst als auch ihr Komplement semi-entscheidbar (also erkennbar) sind.

–> Daher ist also der Schnitt von $RE\wedge coRE$ nur $R$/

Wir wollen uns noch das Komplement einer nicht entscheidbaren Sprache anschauen>

Komplement nicht entscheidbarer Sprachen

wird nicht erkennbar sein

[!Req]

Der Satz besagt jetzt folgend: $L\in RE/⟹L^C\in RE$, also genauer: $L\in RE\setminus R⟹L_C\notin RE$

wie können wir das zeigen? #card

1. Wir wissen bereits, dass $L\in RE\wedge L_C\in RE⟹L\in R$ (das haben wir gerade erst gezeigt!)
2. Ferner wissen wir aber auch, dass $RE\setminus R\ne \varnothing$
3. Und dann können wir jetzt noch konstruieren: Für Sprachen $L\in RE\setminus R$ muss daher folgen, dass $L_C\notin RE$ ist - sonst würden wir einen Widerspruch erzeugen - und damit gilt auch $L\notin coRE$

Also mit den Betrachtung können wir folgend schlussfolgern: $$(L\in RE\wedge L_C\in RE⟹L\in R)⟺L\notin R⟹(L\notin RE\vee L_C\notin RE)$$

Der zweite Part gibt also an, dass wir garantiert sagen können, dass einer der beiden Sprachen ($L\vee L_C$ garantiert nicht in RE sein wird (aber vielleicht in $coRE$))

Wir können jetzt noch ein Beispiel dafür betrachten:

Komplementsprache der universellen TM ist nicht $RE$

[!Bsp] Satz

Es gilt: $A_{TM}^C\in coRE\setminus R$

warum? folgt das? #card

• Wir wissen schon, dass $L\in RE\wedge L\in coRE⟹L\in R$ aussagy
• über die Sprache $A_{TM}$ wissen wir auch $A_{TM}\in RE\setminus R$!
• Dadurch folgt aus Komplement nicht entscheidbarer Sprachen dann -> $A_{TM}\notin coRE⟹A_{TM}^C\notin RE$
• Ferner aber auch: $A_{TM}^C\in coRE$ denn nach Definition $(A_{TM}^C{)}^C{A}_{TM}\in RE$ –> also wenn wir das Komplement des Komplements bilden, müssen wir wieder die Ursprungssprache erhalten, welche $\in RE$ ist!

Bei dieser Beobachtung kann es zur Verwirrung kommen, weil die Komplementbildung bei solche beschriebenen Turingmaschinen teils komisch definiert ist -> also das Komplement ganz anders, als gedacht ist.

$$\begin{array}{rl}{A}_{TM}& =\{⟨M,w⟩\mid M\text{ ist der Code einer Tm, welche w akzeptiert}\}\\ A_{TM}^C& =\{⟨M,w⟩\mid M\text{ ist nicht der Code einer TM welche w akzeptiert}\}\\ D& =\{w_i\mid M_i\text{ akzeptiert nicht}{w}_i\}\\ D^C& =\{w_i\mid M_i\text{ akzeptiert }w\}\end{array}$$

Nachträgliche Betrachtung

Das Konstrukt von $R,RE,coRE$ ist grundsätzlich etwas verwirrend ( aber eigentlich auch richtig gut, weil es eine ungefähre Beziehung der einzelnen Bereiche zueinander darstellen kann)

-> Das Diagramm dazu ist sehr gut zum evaluieren und verstehen!

Was wir hier aussagen wollen:

Per Definition von $coRE$ können wir sagen, dass jedes Komplement einer rekursiv aufzählbaren Sprache $\in RE$ automatisch in $coRE$ liegt ( da wir es genau so definiert / betrachtet haben).

Beispiel für $L\notin RE,\notin coRE$ | $TOT$

[!Definition]

Wir wollen die Sprache (Gott ist) $TOT$ definieren, die einfach die Menge aller Turingmaschinen ist, die eine Sprache bzw kleensche Hülle erkennen kann.

Wie beschreiben wir dei Sprache? Was können wir über sie aussagen? #card

Beschrieben mit: $TOT=\{⟨M⟩\mid M\text{ ha¨lt auf allen }w\in {\Sigma }^{\ast }\}$

Es gilt hierbei - offensichtlich - $TOT\notin RE\cup coRE$

Wir können zeigen, dass $TOT\notin RE\cup coRE$

Das können wir durch eine Reduktion zeigen:

$TOT\notin R$, durch eine Abbildungsreduktion $H_0,{⪯}_{m}TOT$

(klassiche Klausuraufgabe)

Wie können wir jetzt reduzieren?

-> Wir suchen eine explizite Teilmenge aus der zu reduzierenden Sprache und versuchen dann auf die Zielsprache abzubilden.

Betrachte also $H_0:=\{⟨M⟩\mid M\text{ ha¨lt auf }\epsilon \}$ -> Es ist bekannt, dass $H_0\in RE\setminus R$

Dann betrachten wir eine neue Turingmaschine $F(⟨M⟩)=M^{\prime }$ sie hat folgendes Verhalten: $$M^{\prime }(w)=\{\begin{array}{ll}>w\ne \epsilon :& \text{ Halte}\text{ ( das ist mo¨glich, weil Tms berechnen ko¨nnen)}\\ >w=\epsilon L& M(\epsilon )\text{ (ist auch mo¨glich, da sie es erkennen kan)}>\end{array}$$

Dadurch wissen wir, dass diese Funktion berechenbar ist was eine Voraussetzung ist! ( Weil wir damit wissen, dass diese Abbildung von $L_1\to L_2$ (der Reduktion) möglich ist!)

(Das sind jetzt Turingmaschinen, die auf einem leeren Wort nicht halten!

Offensichtlich gilt dann: $M\in H_0⟺M^{\prime }\in TOT$ Und damit ist dann $H_0{⪯}_{m}TOT$ und da $H_0\notin R⟹TOT\notin R$

( Wie können wir mit einer Turingmaschine denn erkennen, ob eine Turingmaschine nicht hält? (Das geht primär nicht,) ))

(Wir müssen noch zeigen, dass $TOT\notin RE$) ( und ferner werden wir auch herausfinden, dass es dann nicht in $\in coRE$ liegen kann ( weil wir gleich zeigen, dass sie nicht $\in RE$ ist!))

Das wollen wir auch durch eine Abbildungsreduktion zeigen: $H_0^C{⪯}_{m}TOT$:

Wir betrachten also $H_0^C:=\{⟨M⟩\mid M\text{ ha¨lt nicht auf }\epsilon \}$ (das haben wir zuvor schon gezeigt) (Sie ist also das Komplement zur vorherigen TM, die auf $\epsilon$ gehalten hat!)

-> Wir betrachten eine neue TM $G(⟨M⟩)=M^{\prime }$ welche folgend funktioniert: $$M^{\prime }(w):\text{ simuliere }M(\epsilon )\text{ fu¨r }\mid w\mid \text{ Schritte. Falls sie unterwegs ha¨lt, LOOP. Sonst HALT}$$

(Das heißt sie wird immer für $\mid w\mid$ Schritte eine SImulation ausführen und danach - wenn sie hält (und somit eine TM $\epsilon$ akzeptiert) in eine Loop übergehen. Ferner wird sie, wenn sie danach noch nicht akzeptiert bzw gehalten hat, einen STOP umsetzen)

–> Damit gilt dann $M\in H_0^C⟺M^{\prime }\in TOT$.

Das Komplement nicht entscheidbarer Sprachen

ist nicht erkennbar: wie zeigen wir das? #card

Dafür nutzen wir folgendne Hilfssatz:

Er sagt aus; Wenn eine Sprache in dem Bereich von $RE$ liegt, dann kann ihr Komplement nichti n $coRE$ sein.

Damit sehen wir, dass es neben $RE$ und $coRE$ noch einen Raum von Sprachen geben, weil der obige Satz sagt, dass eine Sprache $\in RE$ liegt, ihr KOmplement nicht in $coRE$ liegt. Aber es muss ein Komplement existieren, was wir dann “irgendwo anders” verorten müssen.

Es muss sprachen, die rekursiv aufzählbar sind, aber ihr Komplement muss es nicht.

Beispiel $A_{TM}$

Wir wissen, dass $A_{TM}^c\in coRE\setminus R$

Wir können etwa das Beispiel der Turingmaschine und somit die dazugehörige Sprache betrachten: $A_{TM}:=\{⟨M,w⟩\mid \text{ M ist der Code einer TM, welche w akzeptiert}\}$ Ferner aber $A_{TM}^c=\{⟨M,w⟩\mid M\text{ ist nicht der Code eienr TM, welche w akzeptiert}\}$ Wir sehen, dass

(Damit wissen wir, dass die Ursprungssprache in RE liegt und das Komplement ist. Da sie ein Komplement ist, gilt per Definition, dass das Komplement dann in $coRE$ liegen muss!) (Aber es darf nicht in $R$ liegen, weil es nicht entscheidbar und nur erkennbar ist!)

Anders bei $D$: Die Diagonalsprache: $D=\{w_i\mid M_i\text{ akzeptiert nicht }{w}_i\}$ (ist nicht in coRE oder RE! (also außërhalb)) ihr Komplement: $D^c=\{w_i\mid M_i\text{ akzeptiert }{w}_i\}$ (ist coRE) –> Diese Sprache können wir rekursiv aufzählen, weil wir ja einfach die entsprechende Tm nehmen und dann ausfuhren und schauen)

Warum wir aber $D$ nicht rekursiv aufzählen könne: Wir müssten die Eingabe über jede TM laufen lassen und “quasi warten, bis sie es berechnet hat, was eventuell endlos geht (Halteproblem)” und somit können wir maximal erkennen.

Wenn das Komplement einer entscheidbaren Sprachen immernoch in dem Bereich der entscheidbaren Sprachen sit, dann ist sie auch entscheidbar! . Wenn sie nciht entscheidbar aber erkennbar ist, dann muss ihr Komplement dann $coRE$ sein ( was wir per Definition angenommen haben).

Daher die Frage: Befindet sich das Komplement einer nicht entscheidbaren / erkennbaren Sprache dann im Bereich der entscheidbaren Sprachne liegt, wissen wir, wo sie dann in $coRE$ liegt? Also ist sie nur $coRE$ oder auch $R$? (also entscheidbar)

[!attention] Es gibt Sprachen, für die es keine TM gibt, die sie aufzählen kann.

Es gibt aber auch Sprachen die man erkennen, aber nicht entscheiden kann.

Wir wollen jetzt erörtern, ob es möglich ist, einzuschätzen, “ob die meisten Sprachen entscheidbar sind und dieser Randfall einer erkennbaren aber nicht entscheidbaren oft auftritt oder nicht”

Das möchten wir durch Reduktion betrachten und definieren.

Reduktion $⪯$

links lässt sich zu rechts reduzieren:

Idee: Wir wollen von einer schweren Sprache zu einer schweren Sprache abbilden oder zeigen, dass eine Sprache doch leicht ist, weil wir von leicht zu dieser abbilden können.

[!Idea]

Reduktionen verknüpfen ein Problem $P_1$ mit einem anderen Problem $P_2$, sodass dann folgende zwei Aussagen folgen:

welche wären das, was können wir damit dann “anfangen”? #card

Wenn $P_2$ “leicht” ist, dann mussauch $P_1$ “leicht sein”. ( Also wir konnten von 1 auf leicht abbilden und somit auch $P_1$ leicht sein!)

Weiterhin, wenn $P_1$ schwer ist, dann muss auch $P_2$ schwer sein ( weil wir darauf abbilden können!)

Abbildunsgreduktion

[!Definition]

Eine Sprache $L_1\subset {\Sigma }_1^{\ast }$ heißt auf Sprache $L_2\subset {\Sigma }_2^{\ast }$ abbildungsreduzierbar, falls es eine Turing-Berechenbare Funktion $$f:{\Sigma }_1^{\ast }\to {\Sigma }_2^{\ast }$$ gibt, sodass dann $\forall w\in {\Sigma }_1^{\ast }$ gilt: $$w\in L_1⟺f(w)\in L_2$$

Was heißt das konzeptuell, warum brauchen wir diese berechenbare Funktion? Wann heißt diese Funktion dann Reduktion? #card

(Also wir können also einfach von der ersten Sprache auf die andere abbilden, unter Anwendung der Abbildung, die wir definiert haben)

Wir nennen die Funktion $f$ dann die Reduktion von $L_1$ auf $L_2$, beschrieben mit $L_1{⪯}_m{L}_2$ (oder wenn es eindeutig ist, welche Funktion genommen wird, einfach $L_1{⪯}_{}{L}_2$)

Es muss hier also gelten, dass wir jeden Inhalt der einen Sprache durch Anwendung dieser Funktion - welche wir garantiert berechnen können (also sie ist entscheidbar!) - garantiert auf die zweite Sprache abbilden können. –> Wir wollen also aussagen, dass wir eine Äquivalenz zwischen dieser beiden Bereiche finden können!

Wir wissen noch aus 112.14_universal_turing_machine Wann eine Funktion turing-berechenbar / totalrekursiv ist! –> Das tritt genau dann ein, wenn die Eingabe $w\in {\Sigma }^{\ast }$ bei einer TM den Funktionswert von $f(w)$ ausgibt –> Das Wort also garantiert ausgeben kann. (Sie muss hierbei entscheidbar sein!)

Anleitung

[!Tip] Nutzen von Reduktionen

wofür werden Abbildungsreduktionen typischerweise genutzt? Was sind die Schritte dafür? #card

Wir nutzen sie typischerweise, um die Unentscheidbarkeit eines Problems $L_2$ zu zeigen, indem man ein bekannt unentscheidbares Problem $L_1$ darauf reduziert. Also das Beweismuster wäre folgend:

1. Es ist bekannt, dass $L_1$ unentscheidbar ist Also $L_1\notin R$
2. Wir Zeigen, dass $L_1{⪯}_m{L}_2$ und dafür konstruieren wir die Funktion $f$ (TM!) und zeigen dann zwei Dinge:
3. $f$ manipuliert Instanzen aus ${\Sigma }_1^{\ast }$ und hält dabei immer
4. $w\in L_1⟺f(w)\in L_2$

Reduktion und Entscheidbarkeit

Reduktionen entscheidbarer Probleme sind entscheidbar

[!Satz]

Sei $L_1{⪯}_m{L}_2$ dann gilt jetzt folgend:

Welche zwei Aussagen folgen hieraus? #card

1. Falls $L_2$ (semi)-entscheidbar ist, dann ist auch $L_1$ (semi-)entscheidbar! (Denn wir können von L1 auf L2 reduzieren)
2. Falls $L_1$ nicht (semi-)entscheidbar ist, dann ist auch $L_2$ nicht (semi-)entscheidbar (Weil wir diese Komplexität von unserer “schwierigen Sprache” zu der anderen reduzieren (also translatieren können) und somit diese dann auch schwierig sein muss!)

Wir wollen das noch beweisen:

Part 1. Sei $L_2$ (semi-)entscheidbar also es gibt eine TM $M_2$ die $L_2$ (semi-)entscheidet –> Wir konstruieren dann eine TM $M_1$, welche $L_1$ (semi-)entscheidet.

1. Bei einer Eingabe von $w$ wendet dann $M_1$ zunächst die TM $F$ (die die Funktion berechnet) und anschließend wird sie die Ausgabe von $F$ dann bei $M_2$ anwenden –> damit erhalten wir ein Ergebnis, jenachdem, wie wir die Reduktion umsetzen! Part 2. Folgt direkt aus der ersten Aussage –> Denn es ist die Kontraposition: $(A⟹B)⟺(\neg B⟹\neg A)$

Aber es gibt hier auch noch Folgerungen, die uns u.U. nichts neues Aussagen können!:

[!Bsp] Nichtsaussagend!

Sei $L_1{⪯}_m{L}_2$, wobei $L_2$ nicht entscheidbar ist (dann ist also der rechte teil schon schwer, und wir versuchen ein anderes Problem auf dieses zu reduzieren Was können wir daraus folgern? #card

–> was uns nicht aussagen wird) Es folgt nichts für $L_1$

Sei ferner $L_1{⪯}_m{L}_2$, wobei $L_1$ entscheidbar ist. Dann folgt auch hier nichts neues für $L_2$ ()

Ferner wollen wir jetzt viele Beispiele betrachten, die uns helfen, das Konzept der Reduktion verstehen und anwenden zu können.

Leerheitsproblem | nicht Entscheidbarkeit, ob TM etwas akzeptiert

Mit diesem Beispiel möchten wir eine Reduktion exemplarisch durchlaufen und die Idee kommunizieren / beschreiben:

[!Req] Definition des Leerheitsproblem

Wir wollen die Menge von $TM$s finden, die nichts akzeptieren. Ferner beschrieben als:

$$E_{TM}:=\{⟨M⟩\mid M\text{ ist TM und L(M)}=\varnothing \}$$

was können wir über die Sprache aussagen, wie beweisen wir es eventuell? #card

Es gilt dann, dass $E_{TM}\notin R$ –> Also sie ist nicht entscheidbar!

Wir können das etwa durch einen Widerspruch beweisen: Sei dafür etwa $E_{TM}\in R$ dann wissen wir, dass die Sprache $A_{TM}$ ([$A_{TM}$](112.16_nicht_erkennbar_entscheidbar.md#$A_{TM}$)) $\notin R$ liegt! (Also nicht entscheidbar ist).

Wir wollen jetzt zeigen,dass Wenn $E_{TM}\in R$, dann muss auch $A_{TM}\in R$ sein (was ein Widerspruch ist).

Sei dann ferner $R$ eine TM die $E_{TM}$ entscheiden kann. dann bauen wir ferner eine TM $S$, die dann $A_{TM}$ entscheidet ( und bauen eine Abbildung)

Idee für eine Turingmaschine $S$, die wir dann nehmen, um $A_{TM}$ zu entscheiden. Wir bauen eine TM auf, die alle Wörter, die nicht $w$ sind verwirft ( sie quasi das Komplement einer TM, die genau nur ein einziges Wort erkennt und alle anderen verwirft). Wenn jetzt das Wort akzeptiert wird - dann ist es $=w$ und dann simuliert die obig konstruierte TM dann die Eingabe auf die Turing-Maschine $M$.

Auf Input $〈M,w〉$, wende $〈R,〈M〉〉$ an. Wenn R akzeptiert, dann L(M) = ∅ und 〈M, w〉 /∈ ATM. Aber das reicht nicht: Wenn R verwirft wissen wir nichts weiter.

I Stattdessen baut S erst eine erweiterte TM 〈M, w〉 _ M1 die alle w′ 6 = w verwirft, und auf w das gleiche macht wie M. Wenn M1 also irgendein Wort akzeptiert, dann genau w. Wir können nun also R verwenden um zu prüfen ob M das Wort w akzeptiert

Formaler Beweis: Aus der obigen Skizze wollen wir jetzt einen formalen Beweis konstruieren / foldern: Wir nehmen also weiter den Widerspruch an, also $E_{TM}\in R$.

Wir wissen auch, dass $A_{TM}\notin R$ ist Wir zeigen jetzt durch Widerspruch:

1. Definiere TM $M_1$ ide auf Eingabe $⟨w,x⟩$ folgendes macht:
   1. Falls $x\ne w$ –> reject
   2. sonst, simuliere $⟨M,w⟩$ Wir haben noch eine Nebenbedingung! $M_1$ ist relativ zu $w$ konstruiert –> das geht, weil wir den String-vergleichen können 112.12_turing_maschinen
2. Sei $R$ eine TM die $E_{TM}$ entscheiden kann! Dann könnten wir die TM $S$ konstruieren, welche ferner $A_{TM}$ entscheidet!. Sie arbeite bei Eingabe $⟨M,w⟩$ folgend:
   1. Konstruiere wieder $M_1$, wie oben
   2. Wende $R$ auf $⟨M_1⟩$ an - also wir werden entscheiden, ob $L(M_1)=\varnothing$ Falls ja, dann akzeptieren wir und es folgt $⟨M,w⟩\notin A_{TM}$
   3. Ferner Drehen wir die Ausgabe um von $⟨R,⟨M_1⟩⟩$ –> Damit haben wir einen Entscheider S für $A_{TM}$ gefunden, was aber nicht möglich ist (was wir schon wissen!) Es wäre dann $A_{TM}\in R$!

Wir erhalten also, für eine beliebige TM können wir nicht entscheiden, ob sie das Wort erkennt un das ist gleich der Operation, eine TM überhaupt ein Wort erkennen kann.

Haben wir hier gerade reduziert

–> Reduktion kann jenachdem, was man wohin reduziert, falsch sein!

Wir haben gerade gezeigt, dass $E_{TM}\notin R$, indem wir eine “Reduktion” von $A_{TM}$ (schwer) auf $E_{TM}$ (unbekannt) vorgenommen haben Es stellt sich die Frage, ob es eine Abbildungsreduktion war!:

• Die Konstruktion von $M_1$ ist hier eine Abbildung $f$ von $⟨M,w⟩$ auf $⟨M_1⟩$ –> Um $A_{TM}$ zu entscheiden muss die konstruierte $S$ akzeptieren –> was genau dann ist, wenn $L(M_1)\ne \varnothing$ –> Daher muss $M_1\in E_{TM}^C$ dann entscheiden!

Was wir also gerade gemacht haben:

1. Konstruktion einer Abbildung von $f⟨M,w⟩\mapsto M_1(⟨M,w⟩)$ und dann haben wir gezeigt, dass $A_{TM}{⪯}_{E_{TM}^C}$
2. wir wissen auch schon, dass $A_{TM}\notin R⟹E_{TM}^C\notin R$
3. Ferner auch $L\in R⟺L^c\in R$ Also : $$E_{TM}^C\notin R⟹E_{TM}\notin R$$!

Gleicheitsproblem einer TM

Wir möchten noch eine einfachere Reduktion betrachten, die nicht ganz so aufwendig und komplex ist!

[!Definition]

Gleichheitsproblem von zwei TMs, beschrieben mit: $$E{Q}_{TM}=\{⟨M_1,M_2⟩\mid M_1,M_2\text{ sind Tms und }L(M_1)=L(M_2)\}$$

Es gilt: Das Gleichheitsproblem ist nicht entscheidbar!

warum, wie können wir das durch Reduktion zeigen? #card

Wir möchten hier auf die zuvor beschriebene Frage, ob eine TM überhaupt ein Wort akzeptiert, eingehen.

Wir zeigen, dass $E_{TM}{⪯}_{m}E{Q}_{TM}$.

Sei jetzt etwa eine TM $R$ die die Sprache $E{Q}_{TM}$ entscheiden kann.

Dann bauen wir eine neue TM $F$, wie folgt auf:

Sei $M_1$ die triviale TM, die alle Eingaben verwirrft –> also nur in den verwerfenden Zustand übergeht.

Gegeben eines Inputs $⟨M⟩$, setzen wir mit $F$: $⟨M⟩\mapsto R(⟨M,M_2)$ –< Wir entscheiden also mit $R$, ob das Tupel $⟨M,M_1⟩$ in $E{Q}_{TM}$ liegt ( also ob eine bekannte TM, die wir konnstruiert haben, die gleiche Sprache, wie irgendeine andere TM, die auch nichts akzeptiert ist) –> Diese wollen wir also finden!

Dann gilt ferner $⟨M⟩\in E_{TM}⟺F(⟨M⟩)\in E{Q}_{TM}$ und daher folgt: $E_{TM}{⪯}_{E{Q}_{TM}}$

Ferner haben wir also auf das Leerheitsproblem reduziert, weil wir quasi eine konstruierbare leere Turingmaschine nehmen und schauen, ob eine andere TM genau das gleiche macht… Dafür müssen wir aber wieder schauen, für welche Wort eine Turing-Maschine akzeptiert / nicht akzeptiert und ferner, welche/wie viele Wörter sie erkennen kann. Das ist aber wieder durch das Halteproblem nicht entscheidbar!

Folgerungen von Reduktionen

Wir haben gesehen, dass wir von der einen Erkenntnis einer Reduktion direkt auf eine andere reduzieren können –> Wir haben also die Aussagen gechained!

Ferner wird jetzt folgen:

[!Beweis]

Es gilt eine bestimmte Kette von Reduktionen:

Wie stehen die typischen Probleme in Relation zueinander? #card

$${\overline{D}}_{TM}{⪯}_{}{A}_{TM}{⪯}_{}H{⪯}_{}{H}_0{⪯}_{}K$$

Also die Äquivalenz diverser Halteprobleme bzw Umwandlung dieser!

Reduktion von ${\overline{D}}_{TM}{⪯}_{}{A}_{TM}$

Wir kennen schon die nicht-entscheidbare Diagonalsprache $D$ 112.16_nicht_erkennbar_entscheidbar Wir wissen, dass $D$ nicht entscheidbar ist und somit auch das Komplement nicht!

Das können wir konstruieren, indem $\overline{D_{TM}}=\{⟨M⟩\mid M\text{ akeptiert }⟨M⟩\}$

Wir wollen jetzt das Komplement entsprechend auf das Halteproblem reduzieren!

[!Req] Satz | Reduktion von $\overline{D_{TM}}{⪯}_{}{A}_{TM}$

wie können wir das mit einer Reduktion beweisen #card

Wir bilden die Abbildung $f:w\mapsto ww$ was für alle endlichen $w$ berechenbar ist ( einfach copy!)

Offensichtlich gilt jetzt: $w\in \overline{D_{TM}}⟺M\text{ akzeptiert}⟨M⟩⟺f(⟨M⟩)=⟨M,⟨M⟩⟩\in A_{TM}$ und damit wissen wir, dass das Komplement nicht entscheidbar ist!

Reduktion auf allgemeines Halteproblem

Behauptung spezifisches Halteproblem kann man aufs allgemeine Halteproblem reduzieren:

[!Bsp] Behauptung

Folgend sind die Sprachen: $\overline{D_{TM}}=\{⟨M⟩\mid M\text{ akzeptiert}⟨M⟩\}$ $\notin R$ $A_{TM}=\{⟨M,w⟩\mid M\text{ ist der Code einer TM, welche w akzeptiert}\}$ ($\in RE\setminus R$)! $H=\{⟨M,w⟩\mid M\text{ ha¨lt auf Eingabe}w\text{ also verwirft / akzeptiert o. entscheidet}\}$

Wir behaupten jetzt, dass $A_{TM}{⪯}_{}H$

wie können wir das zeigen? #card

(Betrachten wir das Halteproblem: Wir können akzeptieren/verwerfen oder rejecten) Dafür können wir den rejection Zustand einfach entfernen bzw beim eintreten dessen, in einen Endlosloop übergehen und so auch nicht mehr anhalten. Wir haben passend reduziert!

Betrachten wir eine Eingabe $⟨M,w⟩$

Wir konstruieren also die TM $\hat{M}$- mit einem Berechenbarem Code $⟨\hat{M}⟩$ folgend:

• $\hat{M}$ ist identisch mit $M_i$ außer wenn $M$ verwirft, dann geht $\hat{M}$ in eine Endlosschleife!

Dann definieren wir jetzt die Reduktionsabbildung $f(⟨M,w⟩)=⟨\hat{M},w⟩$ und es gilt ferner: $$⟨M,w⟩\in A_{TM}⟺M\text{ akzeptiert w}⟺\hat{M}\text{ stoppt auf w}⟺⟨\hat{M},w⟩\in H$$ Und damit haben wir erfolgreiche reduziert!

Korollar

[!Korollar]

Es gilt $H\notin R$, also das allgemeine Halteproblem ist nicht entscheidbar!

Null-Halteproblem $H_0$

Auch das ist gleichwertig mit dem normalen Halteproblem, wie wir folgend zeigen wollen:

[!Definition]

Wir beschreiben mit $H_0$ folgende Sprache: $$H_0=\{⟨M⟩\mid M\text{ ha¨lt auf Eingabe }\epsilon \}$$–> also auf dem leeren Band!

(Intuitiv ist klar, dass sie auch nicht entscheidbar sein kann, weil es TMs gibt, die womöglich einfach unendlich lang loopen, wenn sie spezifisch $\epsilon$ erhalten –> und man damit nicht entscheiden kann, ob sie es akzeptiert oder nicht!)

Wir behaupten also $H{⪯}_{}{H}_0$!

wie beweisen wir das? #card

Betrachten wir eine Eingabe $⟨M,w⟩$

wir bauen eine TM $\hat{M}$ - wobei wir ihren Code auch berechnen können! - und bauen sie aber spezifisch für das gegeben paar $M,w$:

• Auf Eingabe $\epsilon$ simuliert $\hat{M}$ die TM $M$ auf $w$ (und probiert damit zu schauen, ob die beliebige TM das Wort akzeptiert (was ja $A_{TM}$ ist!))
• anderweitig verwirft $\hat{M}$ (also bei jedem anderen Wort)

Wir bilden jetzt folgende Abbildung: $f(⟨M,w⟩)=⟨\hat{M}⟩$, welche berechenbar ist.

Es gilt jetzt: $$\begin{array}{r}>⟨M,w⟩\in H⟺M\text{ ha¨lt auf }w{⟺}^{\star }\hat{M}\text{ ha¨lt auf }\epsilon \\ ⟺f:(⟨M,w⟩)=⟨\hat{M}⟩\in H_0\end{array}$$

• Weil $\hat{M}$ das Verhalten von $M$ auf w simuliert und $M$ auf w anhält, folgt, dass auch $\hat{M}$ dann auch $\epsilon$ anhält!
• Weil $\hat{M}$ auf $\epsilon$ als Eingabe dann $M$ auf $w$ simuliert und diese anhält, hält dann auch $M$ auf $w$!

(Gleichzeitig wird hier aber auch das nicht-entscheidbar-Problem auftreten, weil wir nicht zwingend wissen, ob auf einer Eingabe $w$ für eine TM $M$ gehalten wird!)

Selbstentscheider - als spezielles Halteproblem | $K$

Wir betrachten noch eine spezifische Sprache:

[!feedback] Selbstentscheider

Sei folgende Sprache: $K=\{⟨M⟩\mid M\text{ ha¨lt auf Eingabe }⟨M⟩\}$ (also sie kann sich selbst lesen und akzeptieren (damit ist sie konzeptuell weiter, als ich und viele andere Menschen!))

Wir behaupten jetzt: $H_0{⪯}_{}K$

wie können wir das beweisen? #card

Wir setzen Vorschläge für $\hat{M}$ so, dass: $$⟨M⟩\in H_0⟺M\text{ ha¨lt auf }\epsilon {⟺}^{\star }\hat{M}\text{ ha¨lt auf }⟨\hat{M}⟩⟺f:(⟨M⟩)=⟨\hat{M}⟩\in K$$

Gleichzeitig gilt aber auch, dass $K{⪯}_{}{\overline{D}}_{TM}⟹K\in RE$ (was abstrus ist?!) –> Beweisen kann man das einfach, indem akzeptieren der Speziallfall beim halten ist!

Reduktion durchführen | Zusammenfassung

Durch diese letzte Reduktion Schließt sich jetzt die gesamte Kette!

[!Idea] Mit einer Reduktion $L{⪯}_{F}R$ einer Sprache $L$ auf eine andere Sprache $R$ durch eine Abbildung $F$ möchten wir folgend aussagen:

“$L$ ist höchstens so schwer, wie $R$” oder “$R$ ist mindestens so schwer, wie $L$!”

warum? #card

Denn wenn man $R$ entscheiden kann, dann kann man auch $L$ entscheiden, indem man jetzt:

1. jede beliebige Instanz aus dem zu $L$ gehörigen Entscheidungsproblem durch $F$ in eine Instanz von $R$ abbildet ($F$ muss berechenbar sein!)
2. diese Instanz aus $R$ muss dann mit dem zugehörigen Entscheider auch entschieden werden.

Beweis führen:

Wir wollen dann also für einen Beweis folgend führen: $$w\in L⟺F(w)\in R$$

Was außerhalb des Bildes von $F$ passiert, ist egal! Wir müssen also etwa nicht zeigen:

• $w\notin R⟹F^{-1}(w)\in L$
• Es muss auch gar nicht die Existenz der Abbildung $F^{-1}$ existieren!

Wir zeigen meist eins von beiden Fällen:

1. $(w\in L⟹F(w)\in R)\wedge (F(w)\in R⟹w\in L)$
2. oder auch: $(w\in L⟹F(w)\in R)\wedge (w\notin L⟹F(w)\notin R)$

Visuell also:

[!Tip] Meistens ist es einfacher diese Probleme von der anderen Seite zu betrachten:

Regularität ist unentscheidbar

ist eine Aussage, welche wir aus der obigen Betrachtung und durch Reduktionen beweisen und ergründen können!

[!Definition]

Sei jetzt folgende Sprache: $$REGULA{R}_{TM}=\{⟨M⟩\mid M\text{ ist TM und }L(M)\in REG\text{ ist also regula¨r!}\}$$

Wir wissen, dass reguläre Sprachen super easy sind –> das waren alle DFAs / NDAs etc!

Es gilt jetzt: $REGULA{R}_{TM}\notin R$ es ist also nicht entscheidbar

warum folgt das? #card

Wir können wieder eine Abbildungsreduktion von $A_{TM}$ zu dieser Sprache machen: $A_{TM}{⪯}_{S}REGULA{R}_{TM}$

Das heißt also, Falls es einen Entscheider $R$ für diese TM gäbe, dann könnte man mit seiner Hilfe auch einen Entscheider $S$ für $A_{TM}$ bauen (was wir ja wissen, nicht möglich ist!)

Idee für einen Beweis: Wir wollen also diesen Entscheider $S$ bauen / konzipieren:

• baue $M$ so zu einer neuen TM um, dass diese eine reguläre Sprache erkennt, genau dann, wenn $M$ das Wort $w$ akzeptieren kann
• Hierzu verwenden wir etwa die Sprache $\{0^n{1}^n\mid n\ge 0\}\notin REG$ und die Sprache ${\Sigma }^{\ast }\in REG$ also einen Anker in $REG$ und $R\setminus REG$

[!Beweis]

Sei $R$ eine TM die $REGULA{R}_{TM}$ entscheidet. Wir konstruieren damit einen Entscheider $S$ für $A_{TM}$ folgend! $S=$ Auf Eingabe $⟨M,w⟩$ mit $M$ und $w\in {\Sigma }^{\ast }$:

1. Konstruiere eine TM $M_2$ auf die Eingabe $x$!
2. Falls $x\in \{0^n{1}^n\mid n\ge 0\}$ dann accept - wir wissen, dass man das realisieren kann! (easy)
3. Sonst simulieren wir $M$ auf $w$ und akzeptieren, wenn wir das Wort $w$ akzeptieren!
4. Wende dann jetzt $R$ auf $M_2$ an!. Falls $R$ akzeptiert, dann accept, sonst reject ( wenn $R$ verwirft!) Damit haben wir einen Entscheider für $A_{TM}$ konstruiert -> was ein Widerspruch ist!

Wichtig:

1. Wir konstruieren $M_2$, nicht, um sie laufen zu lassen. Wir haben sie nur, um es als Eingabe für den Entscheider $R$ zu verwenden!
2. Im Beweis müssen wir darauf achten, dass die Konstruktion von $S$ berechenbar ist!

Zusammenfassung

Wir können viele praktische Inhalte nicht wirklich entscheiden. Also etwa:

• vergleichen von Code, ob er gleich ist
• evaluieren, ob ein Code nach Zeit $n$ einfach abstürzen könnte / oder nicht

Weiter können wir scheinbar manche, interessante Informationen dennoch nicht erörtern?! –> Siehe dafür jetzt theo2_SatzVonRice