BuK-Übung10

Aus ProgrammingWiki
< BuK < IIm11
Archivierte Version vom 2012-06-19T10:52:48+00:00. Aktuelle Version

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:

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

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