Tromp, John
Binary Lambda Calculus and Combinatory Logic
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.
BibTeX - Entry
@InProceedings{tromp:DagSemProc.06051.4,
author = {Tromp, John},
title = {{Binary Lambda Calculus and Combinatory Logic}},
booktitle = {Kolmogorov Complexity and Applications},
pages = {1--20},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2006},
volume = {6051},
editor = {Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2006/628},
URN = {urn:nbn:de:0030-drops-6289},
doi = {10.4230/DagSemProc.06051.4},
annote = {Keywords: Concrete, program size complexity, ambda calculus, combinatory logic, encoding, self-delimiting, binary strings}
}
|
Keywords: |
|
Concrete, program size complexity, ambda calculus, combinatory logic, encoding, self-delimiting, binary strings |
|
Seminar: |
|
06051 - Kolmogorov Complexity and Applications
|
|
Issue date: |
|
2006 |
|
Date of publication: |
|
31.07.2006 |
31.07.2006
