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:DSP:2006:628,
author = {John Tromp},
title = {Binary Lambda Calculus and Combinatory Logic},
booktitle = {Kolmogorov Complexity and Applications},
year = {2006},
editor = {Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
number = {06051},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2006/628},
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
