date-created: 2024-06-20 10:30:26 date-modified: 2024-06-20 06:03:57

Turing Äquivalenz | Vollständigkeit

anchored to 112.00_anchor_overview

Overview

Wir möchten den Sprung von Turingmaschinen als Konzept, zu tatsächlichen Systemen - Computern etc - ziehen. Denn wir wissen, dass moderne Computer kein Band und Schreibköpfe hat / aufweist, wir also dahingehend das Konzept von Speicher etc bisschen anders verstehen und beschreiben.

[!Tip]

Wie kann man etwa eine Programmiersprache passend und formal definieren, sodass sie genauso mächtig ist, wie eine Turing-Maschine?!

Können wir mächtigere Programmiersprachen konstruieren?

Turing-Vollständigkeit / Äquivalenz

Um folglich den Sprung zwischen Programmiersprachen und Architekturen bilden zu können, möchten wir eine Vergleichbarkeit zwischen diesen Konstrukten finden / bauen können.

dabei definieren wir zuerst die Turing-Vollständigkeit (also, dass es etwas alles, was turing–berechenbare-Funktionen sind, berechnen kann) (Wichtig, das ist eine Teilmenge von den Dingen, die eine TM kann!)

Und ferner werden wir noch Turing-Äquivalenz beschreiben und definieren!:

• Das trifft ein, wenn wir genau die gleichen Funtionen, wie eine TM, berechnen können! (Also das Modell ist äquivalent zu Turing-Maschinen (siehe die Dominosteine oder Wang-Tiles 112.19_unentscheidbare_probleme))

Turing-Vollständigkeit

[!Definition] Berechnungsmodell $\mathcal{M}$

Wir möchten dafür das Konzept einer partiellen Funktion betrachten: Sei eine partielle Funktion von $X\to Y$ gegeben, wobei sie hier eine Abbildung von einer Teilmenge $S\subseteq X\to Y$ abbildet (also sie ist nicht auf jede Eingabe definiert!)

Wie können wir das Prinzip jetzt für ein Berechnungsmodell anwenden, wobei wir versuchen beliebige berechenbare Funktionen von ihrem Code zu einer Funktion umzuwandeln? Wann ist ein Programm $P$ dann berchnet von dem Modell? #card

Sei jetzt $\mathcal{F}$ die Menge aller partiellen Funktionen $\{0,1{\}}^{\ast }\to \{0,1^{\ast }\}$ (Also wir schauen uns wieder Kodierungen an, die auf andere abbilden können)

Wir wollen jetzt ein Berechnungsmodell definieren: Es handelt sich um folgende Abbildung: $$\mathcal{M}:\underbrace{\{0,1\}}\text{ etwa eine Go¨delnummer}\to \underbrace{\mathcal{F}}\text{ etwa Funktion, die durch die TM implementiert wird}$$ -> Es kann aber auch ein anderer Code sein, etwa wenn wir unseren Programmcode in Binärsprache translatieren (etwa Python-Compilieren oder so) dann lässt sich das Ganze auch decoded in eine Funktion, die damit umgesetzt wird.

Damit haben wir also von einer beliebigen Codierung eine Abbildung zur korrespondierenden Funktion (die dadurch umgesetzt wird) gezogen. und können jetzt vergleichen.

Ein Programm $P\in \{0,1{\}}^{\ast }$ $\mathcal{M}$-berechnet dann eine Funkion $f\in \mathcal{F}$ (also dem Ziel-Raum der Abbildung), wenn folgend durch die Abbildung folgt: $\mathcal{M}(P)=f$

Aus der Betrachtung können wir nun auch die Turing-Vollständigkeit bestimmen und definieren:

[!Req] Turing-Vollständigkeit

Angenommen wir haben jetzt also ein Berechnungsmodell $\mathcal{M}:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }=\mathcal{F}$ Dann möchten wir jetzt vergleichen können, ob das Berechnungsmodell $\mathcal{M}$ turing-vollständig ist (sein kann).

Was müssen wir dafür tun, um das zu beweisen? #card

Wir können uns jetzt vorstellen, dass wir versuchen werden die Funktionen, die in dem Berechnungsmodell auftreten, auch durch eine TM $M$ umgesetzt werden können.Also:

Ein Berechnungsmodell $\mathcal{M}$ heißt jetzt Turing-vollständig, wenn es eine Turing berechenbare Abbildung $enod{e}_{\mathcal{M}}:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ gibt, sodass folgende Funktion identisch zu einer von einer TM $M$ berechneten Funktion ist: $$f=\mathcal{M}\stackrel{\text{ Programm fu¨r }\mathcal{M}}{\overbrace{encode(\underset{\text{ Go¨delnr. von M}}{\underbrace{⟨M⟩}})}}\in \mathcal{F}$$

Das heißt wir können die Funktion $f$ (welche von einem Programm $P$ umgesetzt wird, anschließend durch die Codierung einer Turing-Maschine, die das gleiche macht, umsetzen)

(Wir können uns das Ganze einfach so vorstellen, dass man den Programmcode, der eine bestimmte Funktion $f$ hat, garantiert in einer TM mit bestimmten Code $⟨M⟩$ ebenfalls umgesetzt werden kann.)

Das können wir jetzt noch erweitern, damit die Beschreibung nicht mehr partiell ist!

Turing-Äquivalenz

[!Beweis] Turing-Äquivalenz

Wir setzen jetzt zwei Attribute dafür, dass ein bestimmtes Berechnungsmodell $\mathcal{M}$ als Turing-Äquivalent eingestuft wird:

welche beiden Attribute müssen für das Modell gelten? #card

Folgend muss gelten:

• es ist Turing-vollständig
• es gibt zusätzlich eine $\mathcal{M}-$berechenbare Abbildung $decod{e}_{\mathcal{M}}$, beschrieben mit : $$decod{e}_{\mathcal{M}}:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$$, sodass $\forall P\in \{0,1{\}}^{\ast }$ (in dem Modell) gilt:$N=decod{e}_{\mathcal{M}}(P)$, wobei dann $N$ eine Gödelnummer einer TM ist, welche die gleiche Funktion, wie $\mathcal{M}(P)$ berechnet!

–> Das bedeutet also ferner auch, dass jedes Programm $\in \mathcal{M}$ eine TM simuliert. –> Damit ist jedes Programm in dem Modell garantiert eine Turing-Maschine (im Konzept zumindest)

While-Berechnungsmodelle

Vorsicht: Wir wollen uns hier von dem While-loop, wie wir ihn kennen, abtrennen, und uns losgelöst von expliziten Programmiersprachen, um die mathematische Definition beschäftigen. –> Wir werden hierbei syntactig sugar herausnehmen, damit wir die Grundlage verstehen und Anwenden können!

Definition

[!Definition]

Wir betrachten nun Strings über einem Alphabet, das aus folgenden Objekten besteht:

1. Abzählar viele Variablen $x_1,x_2,\dots$
2. abzählbar viele Konstanten $0,1,2,\dots$
3. genau drei Keywords $while,do,end$
4. genau sieben Symbole $\leftarrow ,\ne ,;,+,-,[,]$

Ferner haben wir einfache Befehle, dabei gibt es drei verschiedene, die wir betrachten :

• Wertzuweisung $x_i⟵c$
• Addition $x_i⟵x_j+x_k$
• Subtraktion $x_i⟵x_j-x_k$

Unter Betrachtung dieser Voraussetzung möchten wir jetzt rekursiv While-Programme beschreiben:

Wie beschreiben wir jetzt ein while-Programm? #card

Ein While-Programm $P$ ist jetzt entweder ein einfacher Befehl oder hat die folgende Form:

1. einer Schleife, also $while{x}_i\ne 0do{P}_1$
2. einer Verkettung $[P_1:P_2]$ wobei hier $i\in \mathbb{N},P_1,P_2,$ selbst while Programm sind ( sein (eventuell elementar oder halt wieder Ketten!))

Wir haben damit die Syntax von while Programmen definiert. Das heißt, wir haben festgelegt, welche Strings wir als while Programm bezeichnen wollen.

Natürlich ist intuitiv klar, welche Operationen wir damit meinen. Das haben wir aber bislang noch nicht definiert. Wie die Definition der Berechnung einer TM. I Deshalb folgt jetzt die Definition der Semantik, also “was ein while Programm bedeutet”. Die Semantik ist eine partielle Funktion, welche eine Eingabe auf eine Ausgabe abbildet

Semantik | While

[!Req] Semantik | While-Programme

Eingabe: Die Eingabe eines while Programms besteht aus s ∈ N natürlichen Zahlen $\alpha 0,\dots ,\alpha s-1\in \mathbb{N}$ und wird in den Variablen $x_0,\dots ,x_{s-1}$ gespeichert.

Wie können wir dann die Ausgabe beschreiben, wie werden die Variablen belegt? #card

Ausgabe! Falls das Programm anhält, dann ist die Ausgabe der Inhalt der Variable x0 bei Beendigung des Programms. (Wenn das Programm nicht hält, dann ist die Ausgabe nicht definiert)

Ferner beschreiben wir, wie wir speicher hier definieren und beschreiben: Variablenbelegung: Jedes Programm darf hier beliebig viele, jedoch nur endlich viele Variablen benutzen. Sei dabei jetzt $l(P)$ die maximale Zahl an benutzten Variablen. Dann können wir die Variablenbelegung zu jedem Zeitpunkt als einen Vektor ${\mathbb{N}}^l(P)$ schreiben -> Habne wir etwa folgende Startbelegung: $({\alpha }_0,{\alpha }_1,\dots ,{\alpha }_{s-1},0,0,\dots ,0)$ (die Nullen, weil der Speicher da noch frei ist!)

[!Tip] Programmbeschreibung

Sei $S$ die Startbelegung der Variablen. Wir definieren dann rekursiv eine partielle Funktion ${\varphi }_p(S)$, welche die Ausgabe von $P$ bei Eingabe $S$ produziert. Das ist länglich, geht aber nicht anders.

(Das heißt wir können mit dieser partiellen Funktion ${\varphi }_P(S)$ dann einfach eine While-Schleife “)

Wie können wir diese Funktion jetzt für unsere beiden Optionen von While-Programmen umsetzen? Wir haben: $P=x_j⟵c$ und $P=x_i⟵x_j+x_k$ zu Auswahl #card

Wenn jetzt $P=x_i⟵c$, dann beschreiben wir die Funktion folgend: $${\varphi }_P(S)=({\sigma }_0,{\sigma }_1,\dots ,{\sigma }_{i-1},c,{\sigma }_{i+1})$$ und wir haben damit quasi gezählt, bis wir den Index an der Stelle $i$ des Speichers gefunden haben und diesen dann beschrieben mit $c$ –> $x_i$ agiert hier als unser Speichermodell!

Wenn jetzt $P=x_i⟵x_j+x_k$, dann beschreiben wir die Funktion folgend: $${\varphi }_P(S)=({\sigma }_0,{\sigma }_1,\dots ,{\sigma }_{i-1},{\sigma }_j+{\sigma }_k,{\sigma }_{i+1})$$

Also wir haben hier auch einfach die Werte aus bestimmten Indices genommen und dann durch eine Addition an die gewählte Stelle gesetzt –> damit also auch wieder belegt!

Da ${\sigma }_j,{\sigma }_k\in \mathbb{N}$ ist die Operation ${\sigma }_j+{\sigma }_k$ über die Axiome der natürlichen Zahlen definiert und somit möglich!. Wir definieren also die Semantik durch Rückführung auf die natürlichen Zahlen!

Ferner ist die Subtraktion analog: $P=x_j⟵x_j-x_k$ ist folglich $${\varphi }_P(S)=({\sigma }_0,{\sigma }_1,\dots ,{\sigma }_{i-1},\max \{{\sigma }_j-{\sigma }_k,0\},{\sigma }_{i+1})$$

Wir wollen uns auch noch die Verkettung anschauen und werden sehen, dass das auch funktioniert.

[!Req] Verkettung bei While-Schleifen

Angenommen wir haben ein While-Programm: $P=[P_1,P_2]$. Wir wollen das jetzt folgend definieren.

Wie definieren wir es entsprechend? welche zwei Zustände können jetzt auftreten? #card

Falls dieses Programme jetzt also als Kette vorliegt, dann beschreiben wir die Ausführung des Programmes folgend: $${\varphi }_P(S)=\{\begin{array}{ll}>{\varphi }_{P_2}({\varphi }_{P_1}(S))& \text{ falls definiert}\\ >\text{ undefined,}& \text{ sonst}>\end{array}$$ -> Wir schreiben hier ${\varphi }_P^{t)(S}=\underbrace{{\varphi }_P\circ {\varphi }_P\circ \dots {\varphi }_P}r\times (S)$ und meinen also die $r$-fache Verkettung von $P$ auf $S$! Ferner gilt somit auch ${\varphi }_P^{(0)}(S)=S$! (Also die Identität!)

Falls jetzt ferner noch $P=\text{ while }{x}_i\ne 0\text{ do }{P}_1\text{ end}$, dann sei $r\in \mathbb{N}$ die kleinste Zahl, sodass entweder ${\varphi }_{P_1}^{(r)}(S)$ nicht terminiert oder so, dass die $i$-te Variable in ${\varphi }_{P_1}^{(r)}(S)=0$. dann ist folglich: $${\varphi }_p(S)=\{\begin{array}{ll}>{\varphi }_{P_1}^{(r)}(S)& \text{ falls das Programm geendet hat}\\ >\text{ undefined}& \text{ sonst}>\end{array}$$

Also wir können sagen, dass unser Programm eventuell terminieren wird, wenn an der $i$-ten Stelle (im Speicher, also $x_i$) eine $0$ steht, sodass die While-Condition dann erfüllt wird!

–> wenn das nicht passiert, dann wird sie ewig laufen –> somist ist ihr Ergebnis auch undefined!

Wir haben damit nun die Syntax, als auch die Semantik von While-Programmen definiert.

-> Mann kan dann jetzt formal zeigen, dass für jedes $while$-Programm das unsere Definition der Syntax erfüllt, die wir zuvor beschrieben haben, garantiert wohldefiniert sein wird.

[!Attention] While beschreibt Programmiersprachen

Was wir jetzt hier erkennen können: While-Programme beschreiben Programmiersprachen! (Jedoch eine sehr einfache (ohne weitere Definitionen und Syntactic sugar!))

Wir wollen dann jetzt die gängigen Konstrukte von Programmiersprachen in While-Programme überführen, und damit zeigen, dass sie entsprechend alles abdecken kann!

Synctactic Sugar | für While

Anhand mancher Beispiele wollen wir zeigen, dass wir diverse Konstrukte / Operationen umsetzen können: –> Wir wollen also etwa Arithmetiche Operationen und ferner auch Case-Statements explizit übersetzen ( das geht auch für alle anderen Operationen (weil while turing-complete ist!))

Multiplikation

\begin{algorithm} 
\begin{algorithmic} 

\Procedure{product}{$x_j,x_k$}
\State $x_{j} \longleftarrow 0$
\State $c \longleftarrow x_j$
\While{$c \not = 0$}
\State $x_{j}\longleftarrow x_{i}+ x_{k}$
\State $c \longleftarrow c-1$
\EndWhile
\EndProcedure

\end{algorithmic}
\end{algorithm}

und wir sehen, dass sie die Multiplikation relativ elemntar umsetzen kann!

Ferner noch Case-Statements:

\begin{algorithm} 

\begin{algorithmic}  

\Procedure{iftest}{}
\If{$x = 0$} 
\State P
\EndIf

\EndProcedure

\Procedure{asWhileLoop}{}
\State $y=1$
\While{$ x \not = 0$}
\State $y  =0 $
\State $x = 0$
\EndWhile
\While{$y \not = 0$}
\State $y = 0$
\State P
\EndWhile

\EndProcedure

\end{algorithmic}
\end{algorithm}

und damit haben wir passend übersetzen können!

Wir bemerken - später nochmal wichtig! - , dass diese $while$-Ausdrück keine echten Schleifen sind, weil ihr Inneres höchstens einmal ausgewertet wird. Frage ist dabei dann.

[!Attention]

Wir wollen jetzt herausfinden, ob wir andere Paradigmen finden können, die eventuell mächtiger sind, als die soeben definierte While-Schleife

Dafür schauen wir uns ferner ein weiteres bekanntes Paradigma, die For-Schleife an!

For-Programme:

[!Definition]

Wir betrachten dasselbe Alphabet, wie bei den $while$-programmen, wobei das Keyword while durch for ersetzt wird. Ein for-Programm ist dann auch eines von drei Fällen: (Es ist somit beinahe äquivalent zu der Definition des while-Programmes) Dennoch müssen wir wieder 3 Fälle der Definition betrachten!

welche drei Fälle betrachten wir? #card

1. entweder ein einfacher Befehl - $P=x_i=c$ oder eine Addition/Subtraktion (wie bei der while-Schleife) (das können wir dann einfach umsetzen)
2. Es tritt eine Schleife auf! mit folgender Struktur

\begin{algorithm} 
\begin{algorithmic} 
\For{$x_j$} 
\State $P_{1}$
\EndFor
\end{algorithmic}
\end{algorithm}

3. Es kann auch hier eine Verkettung auftreten: $[P_1,P_2]$, wobei auch hier jeweils beide Programme $P_1,P_2$ for-Programme sind!

Wir möchten auch hier wieder die Semantik besprechen und definieren:

[!Req] Semantik von For-Programmen

Betrachten wir For-Programme, so ist ihre Semantik ähnlich - aber nicht gleich - zu while-Programmen.

Wie translatieren wir hier dann ein For-Programm? Spezifisch für das Programm $P=for{x}_{i}do{P}_{1}end$ #card

• Wir werden einfache Programme - also die Zuweisung eines Wertes o.a., wie bei der Semantik von While betrachten.
• Ein Programm $P=for{x}_{i}do{P}_{1}end$ schreiben wir folgende Struktur auf ${\varphi }_P(S)={\varphi }_{P_1}^{x_i}(S)$

Wichtig Was wir durch diese Notation forcieren:

• der Wert von $x_i$ wird nur einmal eingelesen und damit festgelegt, wie oft die Schleife läuft. Das heißt wir können keine Programme formulieren, die innerhalb ihres Codes wieder den Index verändern und somit eventuell endlos lang laufen können / werden.

Wir wollen ferner etablieren / herausfinden, dass alle For-Programme auch durch while-Schleifen umsetzbar sind (so, wie wir schon vorherigen syntactic sugar damit umsetzen konnten)

Alle $for$-Programme sind $while$-Programme

[!Satz] Alle $for$-Programme sind $while$-Programme

Wir wollen folgend beweisen, warum wir eine jede For-Schleife auch als while Programm darstellen können.

Wie gehen wir vor, um entsprechend zu übersetzen / es zu beweisen? #card

Für einfache Befehle und Verkettungen ist die Semantik gleich und daher müssen wir hier nichts beweisen (also Zuweisung etc ist kein Problem)

Jedoch die For-Schleife müssen wir uns anschauen, also “for $x_j$ do $P_1$ end, wobei $P_1$ ein $for$-Programm mit einem bekannten und äquivalenten $while$-programm $P_1^{\prime }$ sein wird. Es gilt jetzt: $${\varphi }_P(S)={\varphi }_{p_1}^{x_i}(S)$$ und wir sehen, dass das äquivalent zu folgendem $while$-Programm sein wird (also ${\varphi }_{P_1^{\prime }}^{(x_i)}(S)$

\begin{algorithm} 
\begin{algorithmic} 
\State $y = x_{i}$ 
\Comment{als neue Variable, die wir nach und nach verringern}
\While{$y \neq 0$}
\State $y = y-1$
\State $P_{1}'$ \Comment{wir führen also die Funktion durch} 
\EndWhile
\end{algorithmic}
\end{algorithm}

Wir haben also eine neue Zählvariable eingeführt, die genau $x_i$-mal die Funktion in der While-Schleife ausfuhren / anwenden wird!

Alle $for$-Programme terminieren immer

[!Feedback] Behauptung

Wir wollen noch behaupten, dass mit unserer Definition! $for$-Programme immer terminieren:

wie können wir das beweisen? #card

(Als Vorüberlegung: Wenn wir eine maximale Zahl der Iterationen setzen, dann werden wir folgend garantiert immer terminieren, weil wir die Schritte eben genau $x_i$ mal ausführen ( und wir verbieten, dass sie diesen Indice verändern!))

Möglich ist das durch eine strukturelle Induktion

IA: ein einfacher Befehl terminiert immer

IS: Sei $P_1$ ein $for$-Programm das terminiert.

• Sei $P=$“for $x_i$ do $P_1$ end”. Dann terminiert ${\varphi }_P(S)={\varphi }_{P_1}^{x_i}(S)$ nach genau $x_i$ Schritten, weil $P_1$ immer terminiert
• Sei $P=[P_1,P_2]$ (eine Verkettung), dann terminiert ${\varphi }_P(S)={\varphi }_{P_2}({\varphi }_{P_1}(S))$ nach endlich vielen Schritten, weil $P_1,P_2$ ebenfalls terminieren müssen!

Damit haben wir genau gezeigt, dass sie terminieren müssen

[!Question]

Was ist, wenn wir eine Schleife konstruieren, die im letzten Schritt, also etwa mit if x-1 = 0 then createNewLoop(), immer wieder eine neue Schleife aufrufen würde - oder vielleicht auch sich selbst?

–> Dann würde sie hier ja eigentlich nicht terminieren, weil sie ja technisch immer und immer wieder rekursiv sich selbst aufruft

GOTO-Programme

Neben While ist auch Goto sehr mächtig - auch wenn es niemand nutzt!(zum Glück xd) - was wir folgend belegen möchten.

[!Definition] $goto$-Programme

Wir betrachten das selbe Alphabet, wie bei while-Programmen, jedoch ersetzen wir ‘while’ mit ‘goto’ und ‘end’ mit ‘halt’.

Damit beschreiben wir jetzt ein $goto$-Programm.

Wie ist es aufgebaut, woraus besteht es? Spezifisch, welche Formen haben die Operationen, und wie beenden wir? #card

Ein $goto$-Programm besteht aus einer endlichen Folge $(1,s_1),(2,s_2),\dots ,(m,s_m)$ von Tupeln (wobei: (Zeilennr, Befehl)) wobei dann jeder Befehl $s_t$ eines der folgenden Formate hat:

• $x_i=c$
• $x_i=x_j+x_k$
• $x_i=x_j-x_k$
• “if $x_i\ne 0$ goto $\lambda$”
• halt

Offensichtlich kann ein solches $goto$-Programm auch wieder in eine Schleife verfallen!:

• (1, $x_1=1$)
• (2, $x_1=x_1+1$)
• (3, $goto2$)

Nach Schöning (Die Semantik solcher Programme sollte klar sein (sie ist ähnlich / gleich, wie bei $while-$programmen))

Aber denken Sie mal drüber nach, wie man sie sauber definiert. (Wichtig, Wenn eine Zeile kein goto enthält, wird danach einfach die nächste folgende Zeile verarbeitet!) –> Variablen können mit Zeilennummern belegt werden!

While | For | Goto | - Berechenbarkeit

Wie auch schon mit 112.12_turing_maschinen können wir Funktion als term-berechenbar einstufen, wobei $term=\{texxxtwhile,for,goto\}$

[!Definition]

Wir wollen ferner eine partielle Funktion $f:{\mathbb{N}}^S\to \mathbb{N}$ while-berechenbar nennen (oder eben auch for/goto-berechenbar)

was muss gelten? #card

Wir können diese partielle Funktion so beschreiben, wenn es ein while-Programm gibt, welches die Funktion berechnet!

for-berechenbar -> while-berechenbar

Wir wissen schon, dass [Alle $for$-Programme sind $while$-Programme](#Alle%20$for$-Programme%20sind%20$while$-Programme) und ferner können wir daraus auch einen Umkehrschluss finden:

[!Feedback] Mächtigkeit von While gegenüber for

Es gilt jetzt: Es gibt $while$-Programme, welche nicht durch $for$-Programme simuliert werden können.

welche, wie können wir das beweisen? #card

kann man mit einem einfachen Gegenbeispiel zeigen: -> Wir wissen ja schon, das $for-$Programm immer terminieren, also wenn wir dann ein while-Programm konzipieren, was nicht anhält, haben wir schon ein Gegenbeispiel!

\begin{algorithm} 
\begin{algorithmic} 
\State $x_{1} =1$
\State $x_{2} = 0$
\While{$x_{1} \neq 0$}
\State $x_{2} = x_{2}+1$
\EndWhile
\end{algorithmic}
\end{algorithm}

Wir sehen offensichtlich, dass man das nicht als For-Programm schreiben kann!

(Es gibt noch ein besseres Beispiel, was wir uns anschauen wollen: Die Ackermann-Funktion!)

$while$-Berechenbar -> $goto$-Berechenbar

Beide scheinen sich ja ähnlich - können nicht terminieren und loopen und laufen irgendwie im Kreis - also wollen wir noch die Äquivalenz beider betrachten:

[!Satz]

Es gilt: Jedes $while$-Programm kann durch ein goto-Programm simuliert werden! Also jede $while$-berechenbare Funktion ist auch $goto$-berechenbar!

wie können wir das beweisen? #card

Dafür möchten wir eine Struktur etablieren, die dabei hilft einfach immer eine $while$-Schleife in ein $goto$-Programm umzuschreiben:

\begin{algorithm} 
\begin{algorithmic} 
\While{$x_{1} \neq 0$}
\State $P$
\EndWhile
\end{algorithmic}
\end{algorithm}

kann man dann etwa folgend mit goto simulieren:

\begin{algorithm} 
\begin{algorithmic} 
\State $M_{1} :~ if~x_{i} = 0 ~ goto M_{2}: P; ~goto`(else)~ M_{1}$
\State $M_{2}: \dots$
\end{algorithmic}
\end{algorithm}

Das geht aber auch in die andere Richtung gut:

[!Req] jedes goto - in while umwandeln (können)

Es gilt: Jedes $goto$-Programm kann durch ein $while$-Programm mit nur einer Schleife simuliert werden! (Also jede $goto$-berechenbare Funktion ist auch $while-$berechenbar)

Wie können wir das folglich beweisen, was wäre der Ansatz zur Übersetzung? #card

Wir können das Programm folgend übersetzen. (Vorab, wir wissen, dass man $if/if-else$ mit while-schleifen darstellen kann!)

Wir translatieren also folgende Struktur:

\begin{algorithm} 
\begin{algorithmic} 
\State $1: A_{1}$
\State $2: A_{2}$
\State $3: A_{3}$
\State $\vdots$
\State $k: A_{k}$
\end{algorithmic}
\end{algorithm}

In folgende Schleife:

\begin{algorithm} 
\begin{algorithmic} 
\State $Zeile~ = 1$ 
\Comment{Gibt den Start an!}
\While{$Zeile \neq 0$}
\If{$Zeile = 1$}
\State $\hat{A_{1}}$
\EndIf
\If{$Zeile = 2$}
\State $\hat{A_{2}}$
\EndIf
\State $\vdots$
\If{$Zeile =l$}
\State $\hat{A_{k}}$
\EndIf

\EndWhile

\end{algorithmic}
\end{algorithm}

Also wir prüfen konstant auf welcher Zeile wir nun sind, um dann die richtige Funktionalität auszuführen und verpacken das in einem Loop!

Ferner beschreiben wir hier noch $\widehat{A_i}$, weil wir da nicht einfach den Code übernehmen können (etwa wenn wir springen, was machen wir dann?)

Wir definiere es demnach folgend: $${\hat{A}}_i=\{\begin{array}{ll}>x_i=x_i\pm x_j;\text{ Zeile}=\text{ Zeile}+1& \text{ falls }{A}_j=(x_i=\pm x_j)\\ >\text{ if}{x}_i=c\text{ then }Zeile=t\text{ else}Zeile=Zeile+1\text{ end}& \text{ falls }{A}_i=(\text{ if}{x}_i=c\text{ goto}t\text{ end})\\ >Zeile=0& \text{ Falls }{A}_j=(halt)>\end{array}$$

Und somit haben wir also immer entsprechend die aktuelle Zeile aktualisiert (passen also auf, dass wir u.U. richtig springen!)

-> bei einfachen Operationen (Arithmetik etwa) werden wir einfach Ausführen und dann auf die nächste Zeile springen (wie beim goto!) Bei einem $goto$-Befehl verändern wir die entsprechend die aktuelle Zeile (welche dann mit den $if$-Conditions abgedeckt werden!) die while-Schleife wird beendet, wenn wir halt im $goto$ finden!

$while⟹while(1)⟺goto$

Es lässt sich aus der Äquivalenz noch ein Korollar aufstellen:

[!Korollar] Kleensche Normalform für $while$-Programme

Es gilt für $while$-Programme:

Jede $while$-Berechenbare Funktion kann durch ein $while$-Programm mit nur einer Schleife berechnet werden

Wie können wir das beweisen? #card

Wir haben ja gesehen, dass man jedes $while$-Programm in ein $goto$-Programm übersetzen kann. Anschließend kann man jedes $goto$-Programm aber auch wieder in ein $while$-Programm mit einer einzigen Schleife übersetzen, wie wir bei [$while$-Berechenbar -> $goto$-Berechenbar](#$while$-Berechenbar%20->%20$goto$-Berechenbar) gesehen haben!

(Tatsächlich stimmt das nur so halb, weil wir ja $if$ etc auch als while-Schleife darstellen müssen und obig nur als syntaktischen Zucker implementiert haben)

While ist Turing-Äquivalent!

[!Attention]

Es gilt auch: $while$ ist Turing-Äquivalent!

(War ja irgendwie klar, als wir gesehen haben, dass $while$-Schleifen manchmal einfach nicht halten)

Turing-Äquivalenz

Beweis

[!Beweis] Strukturelle Induktion

Wir können das durch eine Reduktion von $while{⪯}_{}Turing$ umsetzen (also wir können while-Programme in Turing-Maschinen übersetzen!)

Machen wir dafür eine strukturelle Induktion (wir haben ja auch schon $while$-Programme induktiv definiert!)

Wir führen den Beweis zunächst für den Induktionsanfang der Definition durch, und zeigen dann, wie die TM Konstruktion durch diesen Schritt hindurch funktioniert (also nicht verletzt wird!)

Gegeben sei ein $while$-Programm mit $m$ Variablen.

Wir konstruieren jetzt eine TM mit $m$ Bändern , so dass der Inhalt einer Variable $i$ dann auf dem $i-$ten Band liegt!

Induktionsanfang:

Ein einfacher Befehl ist eine der folgenden drei Anweisungen (nach Definition), wobei $i,j,k,c\in \mathbb{N}$:

• Zuweisung $x_i=c$
• Addition ${}_i=x_j+x_k$
• Subtraktion $x_i=x_j-x_k$

(Intuitiv ist es klar, dass wir arithmetische Operationen mit einer TM darstellen können (haben wir schon in einer Übung gemacht Aufgabe-1))

Induktionsschritt:

ein $while$-Programm $P$ ist entweder ein einfacher Befehl oder hat folgende Form:

• Schleife: “while $x_i\ne 0$ do $P_1$”
• eine Verkettung $[P_1,P_2]$

Wir wollen diese jetzt noch passend umformen, sodass sie von einer TM dargestellt werden können.

1. Sei $M_1$ eine TM, die $P_1$ berechnet / simuliert.

Wir bauen jetzt eine TM $M_{while}$ indem wir - sofern $x_i$ nicht schon existiert - $M_1$ um ein Band erweitern, auf dem dann $x_i$ stehen kann. –> Nach jedem Lauf von $M_1$ liest $M_{while}$ dann $x_i$ aus und ruft ggf dann $M_1$ wieder auf ( wenn die While-Condition noch nicht erfüllt wurde!)

2. Die Verkettung $[P_1,P_2]$ von zwei $TM$s ist auch eine TM!

Sei $M_i$ die TM für das Programm $P_i$. Dann lassen wir jetzt zuerst $M_1$ laufen. Wenn diese TM terminiert dann starten wir $M_2$ auf dem Output von $M_1$ (also Verkettung ist simpel!)

Damit haben wir alle wichtigen Aspekte übersetzt und somit in TMs übersetzt!

Übersicht | Turing-Maschine als PseudoCode

Folgender PseudoCode ist cool, weil man hier ganz gut die Idee und Funktionsweise einer TM erkennen kann! (Man sieht die einzelnen Bereiche (Initialisierung, Übergänge, wann man einen Endzustand erhält etc) sehr klar)

[!bsp] Turing-Maschine als While-Programm

Sei $M=(Q,\Sigma ,\Gamma ,\delta ,q_{accept},q_{reject})$ eine Turingmaschine.

Mit folgendem $while$-Programm können wir die Berechnung simulieren!

\begin{algorithm} 
\begin{algorithmic} 
\Procedure{M}{w} 
\State $q = q_{0}$ \Comment{speichert aktuellen Zustand, ist jetzt der erste}
\State $l=1$ \Comment{l speichert die Position auf dem Band}
\For{$\mid w\mid$}
\state $x_{l} = w_{l}$  \Comment{Lese aktuellen Buchstaben ein}
\state $l = l+1$ 
\Comment{inkrementiere Position}

\EndFor
\state $l=1$ \Comment{resete head}
\While{$T \neq 0$}
\state $(q,x_{l},D) = \delta(q,x_{l})$
\state \Comment{Wir ziehen also die neuen Zustände und Inhalt aus der Übergangsfunktion!}
\state $l = l +D$ \Comment{bewege Kopf}
\If{$q = q_{accept} \lor q  = q_{reject}$}
\Comment{found end condition!}
\state $T = 0$
\EndIf

\EndWhile
\EndProcedure
\end{algorithmic}
\end{algorithm}