cards-deck: university::theo_complexity

Vergleich von Modellen der Berechenbarkeit :

broad part of [[112.00_anchor_overview]]

Bis jetzt haben wir primär Strukturen, wie Endliche Automaten, dann Turingmaschinen betrachtet. Da diese Strukturen sehr abstrahiert bzw nicht wirklich aussagend sind, wollen wir ferner sinnvolle Berechnungsmodelle einführen, die unter Umständen mehr, als eine Turingmaschine können -> oder? Prinzipiell liegt uns nahe, dass wir gerne diverse Modelle, Computermodelle, Programmiersprachen etc mit TMs beschreiben oder vergleichen wollen, denn über diese können wir diverse Aussage treffen und diese dann auch an das verglichene Modell anwenden oder nicht….

Berechnungsmodelle:

Sei $F$ die Menge aller partiellen Funktionen von $\{0,1{\}}^{\ast }$ nach $\{0,1{\}}^{\ast }$. Ein Berechnungsmodell ist dann eine Abbildung #card $M:\{0,1{\}}^{\ast }⟹F$, wobei hier $F$ eine Funktion, die dadurch implementiert wird. Ein Programm $P\in \{0,1{\}}^{\ast }$ $M-$berechnet jetzt eine Funktion $f\in F$ falls $M(P)=f$ ^1686663559926

Turing-Vollständigkeit:

Ein Berechnungsmodell $\mathcal{M}$ heißt Turing-vollständig, wenn es eine turing-berechenbare Abbildung was ist mit dieser gemeint? #card benannt mit $encod{e}_{\mathcal{M}}:=\{0,1^{\ast }\}⟶\{0,1{\}}^{\ast }$ , gibt, so dass sie folgend funktioniert: $\mathcal{M}(encode(⟨M⟩))$ wobei

• $⟨M⟩$ der Gödelnummer der benöþigten Turing-maschine entspricht.
• weiterhin ist $encode(⟨M⟩)$ die binäre Darstellung der neuen Maschine
• und wir bezeichnen $\mathcal{M}$ als die davon berechnete Funktion Wir müssen jetzt resultieren, dass diese neue Berechnung identisch zu der von der TM $M$ Funktion ist. ^1686663559933

Turing-Äquivalenz :

Wir bezeichnen ein Berechnungsmodell $\mathcal{M}$ als Turing-äquivalent, falls folgend gitl #card

• sie ist turing-vollständig, wie obig bereits definiert!. Also wir haben eine Reduktion von $TM⪯\mathcal{M}$
• und wir können eine $\mathcal{M}$-berechenbare Abbildung definieren, die folgend aufgebaut ist: $decod{e}_{\mathcal{M}}:=\{0,1{\}}^{\ast }⟶\{0,1{\}}^{\ast }$, sodass wir dann unter Anwendung $N=decod{e}_{\mathcal{M}}(P)$ die Gödelnummer einer TM erhalten, welche die Funktion $\mathcal{M}(P)$ berechnen kann. Wir haben also eine Reduktion von $\mathcal{M}⪯TM$ vorgenommen. ^1686663559938

While-Programme:

Wir haben zuvor Turingmaschinen als abstrakte Ebene der Berechenbarkeit betrachtet. Wenn wir jetzt auf Anwendungsbezogene Ebenen absteigen, wäre es von Vorteil auch dafür Modelle der Berechenbarkeit zu konstruieren. Wir betrachten dafür zuerst While und If Schleifen / Modelle.

das while-Alphabet :

Um damit eine simple Sprache definieren und beschreiben zu können, setzen wir diverse Basic-Werte: welche? #card

• Variablen: $x_0,x_1,x_2\dots x_n$
• Konstanten: $0,1,2,3,4\dots$
• Key words: while, do, end –> Indikatoren einer speziellen Operation (schleife hier!)
• Symbole: $:=,\ne ,;,+,-,[]$ ^1686663559944

Konstruktion while-Syntax:

while- Programme sind Strings über dem Alphabet der vorigen Folie, die induktiv wie folgt definiert sind: Wir teilen dabei die Konstruktion in zwei Teile auf:

1. einfache Befehle die eine der drei folgenden Anweisungen welche? #card

   1. $x_i:=x_j+x_k$ - einfach arithmetisch
   2. $x_i:=x)j-x_k$ - einfach arithmetisch
   3. $x_j:=c$ Wertzuweisung dabie ist $i,j,k,c\in \mathbb{N}$ ^1686663559949

2. Ein while-Programm P ist entweder ein einfacher Befehl oder hat folgende Form: welche? #card

   1. $while(x_0\ne 0)do{P}_{1}end$ –> also eine Schleife, die ein Programm $P_1$ enthält
   2. $[P_1;P_2]$ was eine hintereinanderausführung von Programmen bezeichnet dabei ist $i\in \mathbb{N},P_1,P_2$ sind while-Programme ^1686663559954

While-Semantik :

Intuitiv ist hier logisch, was gedacht und gemeinet ist. Aber formal bestehen Programme erstmal aus Strings, wir haben noch nicht definiert, wie eine ein/Ausgabe verarbeitet werden kann. Ferner definieren wir diese nun

Eingabe : #card

• Bestehend aus natürlichen Zahlen ${\alpha }_{0,}\dots ,{\alpha }_n\in \mathbb{N}$ und wird in den Variablen $x_0,\dots ,x_n$ gespeichert. ^1686663559958

Ausgabe: #card

• Falls das Programm anhalten sollte(wir können das nicht entscheiden!), dann ist die Ausgabe der Inhalt der Variable $x_0$ bei/nach Beendigung des Programmes. ^1686663559963

Variablenbelegung #card

• Jedes Programm darf beliebig viele, aber nur endlich viele Variablen benutzen. Sei $l(P)$ die maximale Zahl an benutzten Variablen. Dann können wir weiterhin auch die Variablenbelegung zu jedem beliebigen Zeitpunkt als einen Vektor schreiben. Wir können so in etwa die Startbelegung $({\alpha }_0,{\alpha }_1,\dots ,{\alpha }_{s-1},0,\dots ,0)$ darstellen. ^1686663559968

Definition einer partiellen Funktion: Sei S die Startbelegung der Variablen. Wir definieren nun eine partielle Funktion $\upphi{p}(S)$ die :: uns sagt, welche Ausgabe ein Programm $P$ bei Eingabe von $S$ produziert. ^1686663559972 Nennen wir dafür beispielsweise die Startbelegung mit $S=({\delta }_0,{\delta }_1,{\delta }_2,\dots )$ und setzen sie so, dass sie sehr lang ist (tatsächliche Länge ist dabei irrelevant!)

Mit dieser partiellen Funktion $\upphi_{P}(S)$ können wir jetzt diverse Semantiken von einfachen Ausdrücken definieren.

Haben wir beispielsweise $P=x_i:=x_j+x_k$ gegeben. Was kann dann mit der partiellen Funktion berechnet werden? #card Dann gelte unter Anwendung $\upphi_{P}(S) = (\delta_{0},\delta_{1},\ldots, \delta_{i-1},\delta_{j} + \delta_{k}, \delta_{i+1}\ldots)$ –> Also die partielle Funktion findet heraus wo sich unsere Eingaben finden und kann dann die arithmetische Operation passend durchführen, um ein Ergebnis zu erzeugen. In dem Falle wäre das also $x_i$.! ^1686663559976

Betrachten wir den einfachen Ausdruck $P=x_i:=x_j-x_k$ also eine Subtraktion. wie können wir sie mit der partiellen Funktion $\upphi$ berechnen? #card Wenden wir an :$\upphi_{P}(S) = (\delta_{0},\delta_{1}\ldots, \delta_{i-1},\bar\delta_{i}, \delta_{i+1},\ldots)$ wobei wir folgend ${\bar{\delta }}_i:=max\{{\delta }_j-{\delta }_k,0\}$ als das Maxima in dem Bereich bezeichnen. Wir zeigen hier also auch, wie man die Subtraktion berechnet und wo sich das Ergebnis in der Startbelegung befindet. ^1686663559981

Betrachten wir noch folgenden Ausdruck einer Zuordnung: $P=x_i=c$ dann gilt unter Anwendung der partiellen Funktion? #card $\upphi_{P}(S) = (\delta_{0},\ldots, \delta_{i-1},c,,\delta_{i+1},\delta)$ es wird also auch angegeben, wo sich unsere Zuordnung findet, und wo sie sich befinden wird. ^1686663559986

Wir möchten jetzt noch die Semantik der Hintereinander-Ausführung betrachten. Dafür setzen wir voraus: $P=[P_1;P_2]$ wir wird jetzt die partielle Funktion konstruiert und auf diesen Ausdruck angewandt? #card Wir wenden an: $\upphi_{P}(S) = \begin{pmatrix} \upphi_{P_{2}}(\upphi_{P_{1}}(S) ) \text{ falls definiert} \ undefined \text{ sonst }\end{pmatrix}$ Im Folgenden bezeichnen wir noch noch weiter $\upphi_{P}^{(r)}(S)$ als die r-fache Hintereinanderausführung von $P$ gestartet auf S dar. Also wir führen P r-fach auf S aus!. $S⟶S_1⟶S_2\dots ⟶S_r$ ^1686663559990

Semantik der Schleifen: Falls wir mit P ein Programm in Form von “while $(x_i\ne 0)$” do $P_1$ end“ haben, dann setzen wir $r\in \mathbb{N}$ auf die kleinste Zahl, sodass entweder: welche zwei Fälle eintreten können? Wie setzen wir jetzt unsere partielle Funktion? #card $\upphi_{P_{1}}^{(r)}(S)$ nicht terminiert oder die i-te Variable in $\upphi_{P_{1}}^{(r)}(S)$ gleich 0 ist! Tritt dieser Fall ein, setzen wir dann weiter:

• $\upphi_{P}(S) = \begin{matrix} \upphi_{P_{1}}^{(r)}(S) \text{ falls das Programm geendet hat} \ undefined \text{sonst} \end{matrix}$ ^1686663559994

Wohldefiniertheit while-programme: #card

Für jedes while- Programm $P$ ist $Q_p$ wohldefiniert. Diese Struktur könne man anschließend durch eine strukturelle Induktion beweisen. ^1686663559998

Syntactic Sugar:

Was wird mit dem Konzept von Syntactic Sugar(ring) bezeichnet, gemeint? #card Mit der Definition der While-Sprache haben wir bis dato nur ein einfaches Konstrukt angeschaut und gezeigt. Es stellt sich die Frage, ob man mit dieser Sprache jetzt passend andere Operationen aus normalen Programmiersprachen bauen kann. Das heißt: können wir mit der gegebene Sprache andere Terme durch diese Sprache ausdrücken?
^1686663560002

While-Sprache Syntactic sugaring :

Betrachten wir ferner unsere while-Sprache nochmals, um zu schauen, wie wir mit dieser diverse andere Operationen darstellen und bearbeiten können.

Wir können neben den folgenden Basis-Operationen auch noch kompliziertere Konstruktionen, wie Arrays, Stacks etc simulieren.

Arithmetische Operationen:

Alle arithmetischen Operationen auf nat. Zahlen können durch while-Programme beschrieben/geschrieben werden. warum? Wie können wir beispielsweise eine einfache Multiplikation beschreiben? #card Sei $x_i:=x_j\cdot x_k$. Dann können wir sie als While-schleife darstellen:

xi := 0 
count :=xj
while (count != 0) do 
	xi = xi + xk 
	count = count -1 
end

^1686663560005

For-Schleifen :

For-Schleifen können durch while-Schleifen dargestellt werden wie? #card Indem wir beispielsweise die Bedingung einer For-Schleife am Anfang jeder Iteration checken, also beispielsweise $x<=10?$ und dann passend den Wert, der geprüft werden soll, anpassen (beispielsweise dekrementieren o.ä.). ^1686663560009

If-Bedingungen :

Betrachten wir das Statement: “if x = 0 then P end” wie können wir es als eine While-Schleife darstellen? #card

y = 1 
for x do y = 0 end 
for y do P end 

^1686663560013

Wenn x != 0 ist, dann wird y auf 0 gesetzt und dadurch folgt, dass der zweite Loop nicht ausgeführt wird, da dann for y do P end steht und nichts passiert.

For-Programme :

Wir definieren unsere For-Sprache genau, wie die While-Sprache [[#While-Programme]] aber halt mit einem for, statt while!

Ein for-Programm ist entweder ein einfacher Befehl - wie im while-Programm - oder hat welche zwei Formen? #card

1. for $x_i$ do $P_1$ end oder
2. $[P_1;P_2]$ für ein beliebiges $i\in \mathbb{N}$ und für for-Programme $P_1,P_2$ ^1686663560017

Semantik :

Wir haben eine einfche Semantik mit for $x_i$ do $P$ end gegeben. Das heißt also, wenn x verschieden belegt ist, haben wir verschiedene Auswirkungen welche zwei? #card

• Falls $x_i=0$ nichts geschieht!
• Falls $x_i>0$ dann wird $P$ entsprechend oft ausgeführt.
• Wir setzen weiter, dass die Menge der Durchläufe beim ersten Ausführen einmalig gesetzt und nachträglich nicht mehr verändert werden kann. Also die Zählvariable wird einmalig definiert! ^1686663560022

For-Programme terminieren immer:

warum? #card Dies können wir unter Anwendung einer strukturellen Induktion beweisen, in welcher wir angeben, dass nach Definition auf jeden Fall nach $x_i$-Schritten der For-Loop beendet wird!

• Es gibt den Zustand, dass man di Zählervariable ändern kann, um so die Bedingung ins unendliche zu ziehen, jedoch schließen wir das in unserer Definition aus. ^1686663560027

Goto-Programme:

Goto weist prinzipiell das selbe Alphabet wie unsere vorherigen Sprachen auf. Hierbei ist jedoch wichtig, dass eine Eigenschaft hinzukommt: #card

• jede Zeile ist nummeriert, sodass wir auf diese Zugreifen können -> goto springt zwischen Zeilen! ^1686663560031

Definition:

Ein goto- Programm besteht aus einer endlichen Folge (Zeile, Befehl) $(1,s_1),(2,s_2),\dots ,(m,s_m)$ wobei jedes $S_t$ die folgende Form aufweist: welche möglichen Formen setzen wir für die jeweiligen Zeilen? #card

• $x_i=x_j+x_k$
• $x_i=x_j-x_K$
• $x_i=c$
• if $x_1\ne 0$ then goto Line $\lambda$ -> Sprung!
• halt -> Beenden des Programmes ^1686663560036

While vs Turing?

Wir können mit der While-Sprache alle möglichen Operationen von normalen Programmiersprachen durchführen / umsetzen. Das heißt, dass While sehr sehr viel reduzieren kann. Ist es dann vielleicht genauso mächtig, wie eine Turingmaschine? #card

While-Berechenbar: #card

Eine partielle Funktion $f:{\mathbb{N}}^r⟶\mathbb{N}$ nennen wir while-berechenbar, falls es ein while-programm gibt, dass die besagte Funktion berechnen kann. ^1686663560041

For-Berechenbar: #card

Eine partielle Funktion $f:{\mathbb{N}}^r⟶\mathbb{N}$ nennen wir for-berechenbar, falls es ein For-programm gibt, dass die besagte Funktion berechnen kann. ^1686663560047

goto-Berechenbar: #card

Eine partielle Funktion $f:{\mathbb{N}}^r⟶\mathbb{N}$ nennen wir goto-berechenbar_, falls es ein goto-programm gibt, dass die besagte Funktion berechnen kann. ^1686663560053

While vs for vs goto:

Betrachten wir alle drei Sprachen, können wir sagen, dass eine mächtiger als die andere ist? Haben wir vielleicht sogar eine Äquivalenz ( ja )?

Um das herauszufinden, können wir zuerst auf andere Sprachen reduzieren und dann erkennen, ob wir daraus eine Hierarchie finden können:

for $⪯$ while:

for-Programme können durch while-Programme simuliert werden. warum #card Naja, wir können eine While-Schleife setzen, die einfach bei jeder Iteration den Wert der Zählvariable verringern kann. So können wir folgend eine Schleife für die for-schleife definieren!

while $/⪯$ for :

While-Programme können nicht durch ein for-Programm dargestellt werden. #card Zumindest nicht im Allgemeinen, denn for-Programme terminieren immer, während while-Programme dies nicht immer tun. ^1686663560057

steht jetzt also noch aus, was wir über goto und while sagen können. Goto funktioniert prinzipiell wie ein Jump bei Assembler-Sprachen. Mit welchem wir somit durch eine beliebige konstruierte Sequenz arbeiten und sonst springen können. Durch diese Struktur besteht für uns die Möglichkeit, dass wir damit ja auch alle Loops darstellen können oder? Es folgt also:

while $⪯$ goto :

While-Programme können durch goto-Programme simuliert werden. warum? #card

goto $⪯$ while :

Goto-Programme können durch while-Programme ( mit höchstens einer Schleife) simuliert werden! wie können wir das beweisen? Können wir eine Skizze zum simulieren eines Goto-Programmes mit While-Programmen, definieren? #card Ich bin faul und habe die Beweisskizze jetzt einfach herauskopiert. ![[Pasted image 20230613153318.png]] Zur Beschreibung dieser:

• Das while-Programm hat einen Counter, der für uns der Zeilennummer des goto-Programmes entsprechend wird
• Einfache ANweisungen werden einfach ausgeführt und der Counter wird anschließend erhöhrt.
• Bei Goto-Befehlen wird der Counter auf die passende Zielzeilennummer gesetzt, also die while-Schleife wird dann diese Zeile suchen, bis die richtige gefunden wurde. -> Dieser Schritt durchläuft also konstant die Schleife, aber in dieser wird immer mit if-conditions (die wir ja auch mit While darstellen können!) gechecked, ob der counter $⟺$ Zeilennummer mit dem passenden Befehl ist. ^1686663560062

Schlussfolgerung von while = while(1) = goto :

Welche Schlüsse können wir aus der Gleichmächtigkeit von GOTO und WHILE ziehen? #card f ist while-berechenbar $⟺$ f ist while-berechenbar mit while-Programmen, die höchstens eine Schleife haben $⟺$ f ist goto-berechenbar ^1686663560067

Wir möchten gerne weitere Abstrahierungen stattfinden lassen, die uns helfen, ein besseres Verständnis zu diversen Berechnungsmodellen zu setzen. Dabei kann man jetzt rekursive Funktionen betrachten. Siehe dazu [[theo_recursiveFunktionen]]