Thema7

Aufgabe 1

1. Implementieren Sie die Prozedur free mit Scheme im ProgrammingWiki und wenden Sie sie auf selbst gewählte Beispiele an
2. Implementieren Sie die Prozedur bound mit Scheme im ProgrammingWiki und wenden Sie sie auf selbst gewählte Beispiele an

Aufgabe 2

Wenden Sie für ((\lambda x. (\lambda y. (x\ y)))(y\ w)) vor der \beta - Reduktion die \alpha - Konvention an.

Aufgabe 3

Vereinfachen Sie den Racket-Ausdruck (\lambda z.((\lambda x.(y \ x))\ z)).

1. Verwenden Sie die obige \eta-Regel.
2. Verwenden Sie nur die \beta-Regel und vergleichen Sie beide Teilaufgaben-Lösungen miteinander.

Aufagbe 4

1. Zeigen Sie ((\lambda (x) (x\ x))(\lambda (x) x)) und ((\lambda (x) (x\ x))(\lambda (x) (x\ x))).
2. Zeigen Sie, dass für Y := (\lambda (f) ((\lambda (x) (f (x\ x )))(\lambda (x) (f (x\ x))))) gilt: (Y\ g) = (g (Y\ g)).

Aufagbe 5

1. Zeigen Sie, dass es von der Reduktionsreihenfolge abhängen kann, ob die für ((\lambda y. \ z)((\lambda x. \ (x \ x))(\lambda x. \ (x \ x)))) existierende Normalform z gefunden wird oder nicht.
2. Verwenden Sie zur Berechnung von ((\lambda x. \ ((x \ d)(\lambda y. \ (x \ y)) \ a))) \ b) unterschiedliche Reduktionsreihenfolgen.

Aufagbe 6

\lambda xy. x nennen wir einfach true. \lambda xy. y nennen wir einfach false.

Dann gilt if \equiv \lambda txy. txy. (Hinweis: txy \equiv ((t\ x)y))

Berechnen Sie if true e_1\ e_2 = e_1

Aufagbe 7

Currifizieren Sie f(x,y,z) = x + y + z.

Aufgabe 8

Führen Sie

Kreativaufgabe: RAM-Programm

Geben Sie mindestens ein RAM-Programm zur Berechnung der Funktion w:\mathbb{N} \rightarrow \mathbb{N} mit w(n) = \lfloor \sqrt{n} \rfloor an.