Binary Lambda Calculus and Combinatory Logic
John Tromp · WORLD SCIENTIFIC eBooks · 2007
We introduce binary representations of both lambda calculus and combinatory logic terms, and demonstrate their simplicity by providing very compact parser-interpreters for these binary languages. We demonstrate their application to Algorithmic Information Theory with several concrete upper bounds on program-size complexity, including an elegant self-delimiting code for binary strings.