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.

== 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.