DagSemProc.06051.4.pdf
- Filesize: 177 kB
- 20 pages
Document
Binary Lambda Calculus and Combinatory Logic
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6051
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-07-31
Cite As Get BibTex
John Tromp. Binary Lambda Calculus and Combinatory Logic. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06051.4
Abstract
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.
Subject Classification
Keywords
- Concrete
- program size complexity
- ambda calculus
- combinatory logic
- encoding
- self-delimiting
- binary strings
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads