Kombinator-Basen

Def: Eine Menge M mathend000# von Kombinatoren heißt Basis, falls es zu jedem Lambda-Ausdruck einen äquivalenten Ausdruck nur aus Applikationen und Kombinatoren aus M mathend000# gibt.

Satz: {S, K, I} mathend000# ist Basis.

Satz: {S, K} mathend000# ist Basis. -- Beweis? I = … mathend000#

Satz: es gibt eine Basis mit nur einem Element. (Schwer.)

Literatur:

• Henk Barendregt: The Lambda Calculus, its Syntax and Semantics, 1984. http://www.cs.ru.nl/~henk/
• Raymond Smullyan: How To Mock a Mockingbird, 1985. http://www.raymondsmullyan.com/