M. Sperber Sommersemester 1997

Funktionale Programmierung

Blatt 6

Abgabe: 5.6.1997

1. [5 Punkte] Jeder Kombinator kann in einen Ausdruck umgeschrieben werden, in dem nur die Kombinatoren S und K auftreten, nicht jedoch Abstraktionen. Es reicht jedoch auch ein einziger Basiskombinator aus. Beweisen Sie dies, indem Sie zeigen:

   

2. [10 Punkte] Führen Sie den Beweis von Satz 1.14 zu Ende. D.h.: Beweisen Sie, daß es Kombinatoren , , gibt mit:

   

3. [5 Punkte] Zeigen Sie, daß F mit der folgenden Definition ein Fixpunktkombinator ist:

   

4. [10 Punkte] Wie lassen sich im -Kalkül verschränkt rekursive Funktionen definieren? Formulieren und beweisen Sie einen entsprechenden Fixpunktsatz.

• Über dieses Dokument ...