BuK/IIm11/BuK-Übung10

Wiki-Quelltext dieser Seite.

== Beweisidee (Max Wielsch) ==
Entwickeln Sie eine Beweisidee zu folgendem Satz:

Jede primitiv-rekursive Funktion ist LOOP-berechenbar und
umgekehrt.

LOOP-Programme sind gekennzeichnet durch folgende Konstrukte:
* Wertzuweisungen (Bindung an Variablen)
* Konstanten
* Iterationen / Zyklen (LOOP <Wert> DO <Sequenz> END)
* Programmaufrufe

weiterhin ist von vornherein bekannt, wie viele Zyklen ein LOOP-Programm durchläuft.

Primitiv-rekursive Funktionen sind wie folgt definiert:
* Es gibt Basisfunktionen, die allesamt total und berechenbar sind.
** Nachfolgerfunktion
** Nullfunktion
** Projektionsfunktion
Mit diesen Basisfunktionen und den 2 folgenden Techniken können weitere Funktionen beschreiben werden:
* Primitive Rekursion
* Substitution

Nun können die Konstrukte aus der LOOP-Sprache wie folgt den Vorschriften der primitiv-rekursiven Funktionen zugeordnet werden.

* Variablen können der Zahl den Parametern in der Funktionsdefinition zugeordnet werden
* Konstanten können durch die Nullfunktion erreicht werden.
* Zyklen werden durch die primitive Rekursion erreicht.
* Programmaufrufe entsprechen Substitution

Umgekehrt kann zugeordnet werden:

* Die Nachfolgerfunktion kann durch die primitiv-rekursive Funktion add realisiert werden
* Die Projektionsfunktion bedeutet in LOOP-Programmen einen Programmaufruf mit n Argumenten.

== Begründung (Raik Bieniek) ==
Begründen Sie, weshalb Polynome mit natürlichen Koeffizienten primitiv rekursiv sind.

Beispiel $p(n)=an²+bn+c.$

Polynome bestehen nur aus Additionen, Multiplikationen und Potenzierungen. Diese sind bereits als primitiv rekursiv nachgewiesen.

Für das Beispiel:

$p(n)=add(mult(a,pot(n,2)),add(mult(b,n),c))$

== Berechnung (Felix Nitsche, Stefan Lüttke) ==
Der rumänische Mathematiker Gabriel Sudan (14.04.1899 - 22.06.1977) - wie Ackermann ebenfalls ein Schüler von David Hilbert - hat 1927 eine total berechenbare jedoch nicht primitiv rekursive Funktion publiziert.
Sie ist folgendermaßen definiert:

<math>
F_0(x,y)=x+y\\
F_{n+1}(x,0)=x,n\geq0\\
F_{n+1}(x,y+1)=F_n(F_{n+1}(x,y),F_{n+1}(x,y)+y+1),n\geq0
</math>

Berechnen Sie F1 und F2 für selbstgewählte Argumente.