Seien M, N und P Lambda-Terme. Zeigen oder widerlegen Sie: Wenn M aus SubxN[P] entsteht, gilt

1. FV(M) = ( FV(P)-{x} U FV(N) ) und
2. BV(M) = ( BV(P) U BV(N) )

Zeigen Sie: Der -Kalkül wird inkonsistent, wenn man die Axiome um die Regel xy.yx = x.x erweitert.

Konstruieren Sie einen -Term, dessen Normalform aus mindestens 10¹⁰ Zeichen besteht.

Gegeben seien die bekannten Kombinatoren (also geschlossene -Terme) Ix.x, Kxy.x und Sxyz.xz(yz).

1. Konstruieren Sie einen Kombinator M mit der Eigenschaft MS = M
2. Konstruieren Sie einen Kombinator M mit der Eigenschaft MISS = MS
3. Zeigen Sie: Für XSI gilt XXXX = X(X(XX))