Prof. Dr. R. Laue
Dr. A. Kohnert                                                                                                                                             SS 2005
Compilerbau und formale Sprachen
                                Übungsblatt 13
                              

URL:         /axel/compiler_ss05_blatt13.html

 Dieses Blatt wird am 13.7.2005 besprochen.




Aufgabe 31 primitiv rekursiv 
 

Zeigen Sie, dass ganzzahlige Division und Divisionsrest primitiv rekursiv sind.



Aufgabe 32 Ackermann Funktion

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 33 Ackermann Funktion (source code mitbringen)

Implementieren Sie die grosse Ackermann Funktion per rekursivem Unterprogramm in einer Programmiersprache Ihrer Wahl. Lassen Sie das Programm   laufen. Es sollte für die meisten Parameter Werte relativ schnell abstürzen. Warum?