cards-deck: university::theo_complexity

Das Halteproblem und viele weitere Probleme in $RE\setminus R$ :

specific part of [[theo2_ReduktionenBerechenbarkeitstheorie]] broad part of [[112.00_anchor_overview]]

Wir möchten folgend eine Kette von Reduktionen betrachten und daraus weiter Schlüsse über TMs und Berechenbarkeiten ziehen:

$\overline{D_{TM}}⪯A_{TM}⪯H⪯H_0⪯K$ Wir wollen jetzt folgend betrachten, dass: $\overline{D_{TM}}$ unentscheidbar ist und so weiterhin auch alle folgenden Probleme unentscheidbar sein werden!

Alle angegebenen Sprachen in der Kette obig wurden in früheren Dateien bereits bearbeitet und definiert.

Außerdem möchten wir betrachten, dass K semi-entscheidbar ist. Daraus können wir dann schließen, dass alle anderen Probleme weiter vorn in der Kette auch semi-entscheidbar sind.

Reduktion von $\overline{D_{TM}}⪯A_{TM}$: #card

Ferner eine Wiederholung der Definitionen: $\overline{D_{TM}}=\{⟨M⟩|M\text{akzeptiert}⟨M⟩\}$ $A_{TM}=\{⟨M,w⟩|M\text{ akzeptiert}w\}$ Wir möchten ferner annehmen (und später beweisen), dass $\overline{D_{TM}}⪯A_{TM}$ Die Reduktion ist eigentlich trivial, denn definieren wir $f(w):=ww$. Dann ist dies berechenbar und offentsichtlich gilt folgendes: $w\in \overline{D_{TM}}⟺M\text{ akzeptiert }⟨M⟩⟺f(w)=ww\in A_{TM}$ ^1684878506134

Reduktion von $A_{T}M⪯H$(und das Halteproblem): #card

Ferner eine Wiederholung der Definitionen: $A_{TM}=\{⟨M,w⟩|M\text{ akzeptiert}w\}$ $H=\{⟨M,w⟩|M\text{ ha¨lt bei Eingabe w an}\}$ –> also terminiert tatsächlich! Wir möchten jetzt behaupten: $A_{T}M⪯H$, Wie? Beweis: Sei die Eingabe $⟨M,w⟩$ gegeben. Wir bauen eine neue Tm $M^{\sim }$ wie folgt: $M^{\sim }$ macht die gleichen Berechnungen, wie $M$. Nur falls $M$ in einen nicht-akezptierten Zustand stopp, dann begibt sich $M^{\sim }$ in eine Endlosschleife und stoppt nicht. Sei $⟨M^{\sim }⟩$ der Coder der diese TM dann beschreibt. Den Code von $M^{\sim }$ können wir dann berechen. Wir stellen dafür eine Reduktionsabbildung auf: ^1684878506142

$f(⟨M,w⟩)=⟨M^{\sim },w⟩$ Es gilt damit jetzt: $⟨M,w⟩\in A_{TM}{⟺}^{\text{definition von ATM}}M\text{ akzeptiert w}|Longleftrightarrow{M}^{\sim }\text{ stopp bei der Eingabe w}$$undweitergiltdannauch:$\Longleftrightarrow \langle M^{\sim},w \rangle \in H$ –> also es entspricht der Sprache H!

Reduktion $H\preceq H_{0}$: #card

Ferner eine Wiederholung der Definition der Sprachen: $H = {\langle M,w \rangle | M \text{ hält bei Eingabe w an} }H_{0}= {\langle M\rangle | M \text{ hält bei der Eingabe des leeren Wortes an }=\epsilon }$Wir\ast \ast behauptenjetzt\ast \ast :$H\preceq H_0$:Wie?\ast \ast Beweis\ast \ast :SeidieEingabe$\langle M,w\rangle$vomProblemHgegeben.DannbauenwirjetzteineTM$M^{\sim}$folgend:Fallseine\ast \ast Eingabevon$M^{\sim}$dasWort$\epsilon$\ast \ast ist,dannsimuliertdieMaschine$M^{\sim}$dieTMMauf$w$.FallsdieEingabevon$M^{\sim}$ebennicht$\epsilon$ist,dannhaltdieMaschine$M^{\sim}$einfachan.Sei$\langle M^{\sim}\rangle$ dann der Code dieser Tm. $M^{\sim}$h\ddot{a}ngtdannalsovonMundwab,beidesistfesteinprogrammiertinderTM{.}_{W}irwollenjetztdieReduktionsfunktion$f(\langle M,w\rangle):= \langle M^{\sim}\rangle$definieren.MitdieserStrukturgiltdann:$\langle M,w\rangle \in H\Longleftrightarrow M\text{ hält auf w an}$Weiterfolgtdann:$\Longleftrightarrow M^{\sim}\text{ hält bei der Eingabe des leeren Wortes an}$unddarausschließtsichdann:$\Longleftrightarrow f(\langle M,w\rangle ) = \langle M^{\sim}\rangle \in H{0}$wasgenauderDefinitionderSprache$H_{0}$entspricht!1.$M^{\sim}$simulierendann,wasMaufwtutundMh\ddot{a}ltjaan.2.Wenn$M^{\sim}$dieEingabe$\epsilon$ kriegt, simuliet sie M auf w. Diese Simulation hält genau dann an, wenn M auf w anhält ^1684878506147

Reduktion $H_{0}\preceq K$: #card

Wiederholung der benötigen Definitionen: $H_{0}= {\langle M\rangle | M \text{ hält bei der Eingabe des leeren Wortes an }=\epsilon }K={\langle M\rangle | M \text{ M hält bei Eingabe von}\langle M\rangle~~an}$\ast \ast EsfolgtdieBehauptung:\ast \ast$H_{0}\preceq K$:Wiezeigen?Wirk\ddot{o}nnenwiebeidenvorherigenBeweiseneinepassendeTm$M^{\sim}$definieren,dieentsprechenddieEingabenvonderanderenTMerh\ddot{a}ltundrichtigbearbeitenkann.DarausfolgtanschließendeinepassendeReduktions-Funktion,dieunserProblemauf$K$ reduzieren kann. ^1684878506152

Ergebnisse aus den Reduktionen: #card

![[Pasted image 20230523153248.png]] Was können wir aus der folgenden Reduktion schließen ? $\bar{D_{TM}} \preceq A_{TM}\preceq H \preceq H_{0}\preceq K$::DieSprachen$\bar{D_{TM}},A_{TM},H,H_{0},K$sindallein$RE\setminus R$ beinhaltet. ^1684878506158 ^1684878506162

Anwenden von Reduktionen: #card

Wir wollen beweisen, dass eine Sprache $L$(Semi-)entscheidbaris.\ast \ast Daf\ddot{u}r\ast \ast m\ddot{u}ssenwiralsoeineSprache$L^{\sim}:~L\preceq L^{\sim}$,sodass$L^{\sim}$dann(semi-)entscheidbarist.\ast \ast Weiterhinm\ddot{o}\stackrel{\backslash c}{c}htenwirbeweisen\ast \ast dasseineSprache$L$eventuellnicht(semi-)entscheidbarist.Daf\ddot{u}rm\ddot{u}ssenwireineSprache$L^{\sim}$konstruieren/finden,die$L^{\sim}\preceq L$sodass$L^{\sim}$ dann nicht (semi-)entscheidbar sind. ^1684878506165 ^1684878506171

Interpretation des Halteproblems: #card

Was können wir aus dem Halteproblem schließen und was sagt es aus? Warum wäre ein solches Konstrukt sinnvoll und erwünscht? Das Halteproblem ist ein Problem, dass in der Informatik sehr wichtig ist. Es wäre von Vorteil, wenn man es lösen könnte, was jedoch nicht möglich ist. Unter der Anwendung des Halteproblemes könnte man Code eines Programmes betrachten und mit einer TM bzw. einem anderen Code betrachten, ob der Code des Programmes immer terminieren und somit nie in eine Endlosschleife verfallen kann oder wird. Das funktioniert nicht, denn wenn wir warten, um ein Ergebnis eines Programmes zu betrachten, wissen wir nie, ob es noch terminiert oder nicht. Wir können X Jahre warten und es als endlos deklarieren, dennoch könnte es kurz danach terminieren!

Wir könnten also die Richtigkeit und Determinismus eines Programmes beschreiben, das geht aber leider nicht. ^1684878506176

Das Halteproblem ist unentscheidbar!

Nutzen: Man könnte somit wichtige Programme in ihrer Funktion beweisen, und somit Flugzeuge / Atomkraftwerke mit sicherer, funktionierenden Software gestalten

Es gibt also sehr relevante Probleme, die von einer TM nicht gelöst werden können!

Variante des Halteproblemes: #card

Betrachte die Menge $T ={ | M \text{ hält auf jeder Eingabe an}}$WaskannmannausdieserBetrachtungeineranschließendenReduktionbetrachten?MankanndurchdieseReduktionzeigen,dass$T\not \in RE$gilt.DasGleichegiltdannauchf\ddot{u}r$\bar T$\ast \ast Bemerkungdazu\ast \ast :WirhabenalsoeinBeispielf\ddot{u}reineSprachegefunden,wo\ast \ast sowohldieSprache\ast \ast selbst,alsauchihr\ast \ast Komplement\ast \ast nichtin$\not \in RE$ sind. ^1684878506181

Beispiele die aus dem Halteproblem folgen:

Berechnen zwei TMS das Gleiche? #card

Seien $M_1$und$M_{j}$dieIteundJteTuringmaschine.K\ddot{o}nnenwirtesten,obsievielleichtdasGleicheberechnen?Alsogebensieauf\ast \ast jederEingabe\ast \ast diegleicheAusgabe?Seidaf\ddot{u}r$M_{i}$dieSpezifikationeinesProgrammesund$M_{j}$dieaktuelleImplementierungdieser.Erf\ddot{u}lltdieImplementierungdanndiegeforderte\ast \ast Spezifikation\ast \ast ?Umdieszul\ddot{o}senkonstruierenwirnuneineSprache:$V= {\langle M_{1},M_{2}\rangle | \forall w:M_{1}(w) = M_{2}(w)}$MankannmitderReduktiondannzeigen,dass$V\not \in RE$gilt.Somitgiltdadannauch$\bar{V} \not\in RE$ ! ^1684878506186

Ausblick | Definition von Turing-Reduktionen: #card

WIr haben uns bisher nur Abbildungs-Reduktionen angeschaut. Es gibt eine allgemeinere und mächtigere Implementation eine Turing-Reduktion Betrachten wir zwei Probleme und weiter: Problem 1 ist $\preceq$ Problem 2, falls es eine TM zur Lösung von Problem 1 gibt, die eine Turingmaschine für Problem 2 beliebig oft als Unterprogramm aufrufen darf. Further sources to be found in : [Sips,er Kap 6.3] ^1684878506192

Ausblick | Definition von Reduktion in der Komplexitätstheorie:

Bisher haben wir immer nur in leichte und schwere Probleme im Kontext der Berechenbarkeit unterteilt. Dabei war

• leicht $\Longrightarrow$(semi-)entscheidbar-\ast \ast schwer\ast \ast$\Longrightarrow$nicht(semi-)entscheidbarWirm\ddot{u}ssendabei\ast \ast sicherstellen\ast \ast ,dassdieReduktionvon$f$selber\ast \ast leicht\ast \ast alsoberechenbarist,sonstbrichtdas\ast \ast Argumentzusammen\ast \ast ,mitwelchemwirweiterf\ddot{u}hrendSchlussfolgerungenziehenwollen.Sp\ddot{a}terwerdenwirf\ddot{u}\acute{y}die\ast \ast Komplexit\ddot{a}tstheorie\ast \ast nochweitere\ast \ast Reduktionen\ast \ast betrachtenk\ddot{o}nnen.DawerdendieBegriffeneudefiniert:\ast \ast leicht\ast \ast$\Longrightarrow$schnellberechenbar\ast \ast schwer\ast \ast$\Longrightarrow$nichtschnellberechenbarsieheauch[[111.00_{a}nchor]]Wirm\ddot{u}ssendannfordern,dassdieReduktion$f$ selbst leicht also schnell berechenbar ist, damit wir auch weitere Beobachten und Konvertierungen durchführen können,