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 AsGet 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
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.
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