While-True (WHILE, LOOP)

WHILE

WHILE ist das einfachere von beiden...

Die Programmiersprache WHILE ist sehr simple, sie besteht aus:

• Variablen: $x_0, \dots, x_n$
• Konstanten: $-1, 0, 1$
• Symbolen: $;, :=, +, \neq$
• Schlüsselwörtern: $WHILE, DO, END$

Die Syntax ist wie folgt definiert:

• $x_i := x_j + 1$ ist eine Zuweisung
• Sind $P_1$ und $P_2$ Programme, so ist $P_1; P_2$ ein Programm, das zuerst $P_1$ und dann $P_2$ ausführt
• Ist $P$ ein Programm, so ist WHILE $x_i \neq 0$ DO $P$ END ein Programm, das $P$ solange ausführt, bis $x_i = 0$ ist

Weitere Semantik:

• Die Eingabe ist in den Variablen $x_0, \dots, x_n$ gespeichert. Der default Wert = 0
• Die Ausgabe ist in den Variablen $x_0, \dots, x_n$ gespeichert

Guckt hier später vorbei ich liste dann die Programme auf die wir schon hatten (ich muss dringend lernen uff):

WHILE ist Turingmächtig

LOOP

LOOP ist das erste Berechnungsmodell, das nicht Turingmächtig ist, dafür garantiert es uns aber, dass eine Programm immer anhält.

Die Programmiersprache LOOP ist sehr ähnlich zu WHILE und besteht aus:

• Variablen: $x_0, \dots, x_n$
• Konstanten: $-1, 0, 1$
• Symbolen: $;, :=, +, \neq$
• Schlüsselwörtern: $LOOP, DO, END$

Die Syntax ist wie folgt definiert:

• $x_i := x_j + 1$ ist eine Zuweisung
• Sind $P_1$ und $P_2$ Programme, so ist $P_1; P_2$ ein Programm, das zuerst $P_1$ und dann $P_2$ ausführt
• Ist $P$ ein Programm, so ist LOOP $x_i$ DO $P$ END ein Programm, das $P$ $x_i$ mal ausführt. WICHTIG: $x_i$ darf nicht in $P$ vorkommen!

Weitere Semantik:

• Die Eingabe ist in den Variablen $x_0, \dots, x_n$ gespeichert. Der default Wert = 0
• Die Ausgabe ist in den Variablen $x_0, \dots, x_n$ gespeichert

Ackermannfunktion

Die Ackermannfunktion ist unser Beweis, dass LOOP nicht Turingmächtig ist. Da sie schneller wächst als jede Berechenbare LOOP Funktion.

Die Ackermannfunktion ist definiert als $A: \mathbb{N} \to \mathbb{N}$:

• $A(0,n) = n+1$ für $n \ge 0$
• $A(m+1, 0) = A(m, 1)$ für $m \ge 0$
• $A(m+1, n+1) = A(m, A(m+1, n))$ für $m, n \ge 0$

Monotonie Eigenschaften der Ackermannfunktion sind:

• Strickte Monotonie in der zweiten Komponente: $A(m, n+1) > A(m,n)$ für alle $m, n \in \mathbb{N}$
• Diagonale Monotonie: $A(m+1, n) \ge A(m, n+1)$ für alle $m, n \in \mathbb{N}$

Falls ihr eine Monotonie Eigenschaft in der Klausur Beweisen müsst !vollständige Induktion! verwenden. (Falls ihrs Vergessen haben: (Induktionsanfang) $\to$ (Induktionsvoraussetzung) $\to$ (Induktionsschritt))