Im Script ist beispielhaft eine funktionale Enwicklung der Fakultätsfunktion angegeben. Enwickeln Sie analog funktionale Definitionen z.Bsp. für

1.  für n <= 1 :   F(n) := 1
    für n > 1  :   F(n) := F(n-1) + F(n-2)
   	  

2.  für n = 1 :    F(n) := 1
    für n > 1 :    F(n) := n + F(n-1)	  
   	  

3. die Determinanten-Funktion

Geben Sie die Definition einer Turing-Maschine an, und finden Sie Referenzen für die Beweise der wichtigen Aequivalenzsätze für berechenbare Funktionen (TM-berechenbar, RM-berechenbar, µ-rekursiv, -berechenbar). Skizzieren Sie die Beweisideen für einige der Aequivalenzen.

Betrachten Sie die Umsetzung der "Funktion" lambda in einem Lisp-System (z.Bsp. xemacs-Lisp), und programmieren Sie eine der Funktionen aus Aufgabe 1 damit.

Finden oder geben Sie eine alternative Definition des Lambda-Kalküls (d.h. ohne die Verwendung einer Grammatik)

Sei ein reiner Lambda-Kalkül mit der Variablenmenge {x, y, z} gegeben. Sind die folgenden Ausdrücke Terme dieses Kalküls in strenger bzw. konventioneller Notation?

1. xyx
2. .xyx
3. x.yx
4. xy.x
5. xyx.
6. x.xx(x.xx)
7. xyx
8. xy.3*x
9. xy(xy)
10. y(xy)
11. yxy
12. x.xyx.zx

Wandeln Sie die Terme aus Aufgabe 5, soweit möglich, in die strenge Darstellungsform um. (Ergänzen Sie dabei ggf. Kammmerungen, wenn damit gültige Terme zu erhalten sind)