Prof. Dr. R. Laue                                                                                                                                  WS0203
                                Informatik III
                                Übungsblatt 12
                                Abgabe: 30.1.03 vor der Vorlesung 

URL:         /axel/informatik3_ws0203_blatt12.html
Dieses  Übungsblatt ist in Zweiergruppen zu  bearbeiten.
 

Aufgabe 29 primitiv rekursiv  (5 Punkte)
 

Zeigen Sie dass ganzzahlige Division und Divisionsrest primitiv rekursiv sind.



Aufgabe 30 Ackermann Funktion (4+6 Punkte)

Die i-te Ackermann Funktion Bi(x)  wird rekursiv definiert:

B0(0) := 1; B0(1):= 2; B0(x) :=x+2 falls x>=2.

Bi+1(x) := Bix(1)

dabei bedeutet  Bix die x-fache Komposition, wobei x=0 die Identität bei der Komposition von Abbildungen ist, d.h. die Funktion x |--> x. Die grosse Ackermann Funktion wird definiert als
A(i,x):= Bi(x)
Zeigen Sie:
1) Bi(x) ist primitiv rekursiv.
2) Monotonie in allen Parametern:

- Bix(y) <  Bix(y+1)
- Bix(y) <  Bix+1(y)
- Bix(y) <=  Bi+1x(y)               für alle i,y,x


Aufgabe 31 Ackermann Funktion (3 Programmierpunkte, Abgabe source code auf Zettel)

Implementieren Sie die grosse Ackermann Funktion per rekursivem Unterprogramm. Lassen Sie das Programm auf dem Linux CIP pool  laufen. Es sollte für die meisten Parameter Werte relativ schnell abstürzen. Warum?