DROPS

Document

Binary Lambda Calculus and Combinatory Logic

Authors: John Tromp

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

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.

Cite as

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.06051.4},
  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}
}

Search Results

Documents authored by Tromp, John

Binary Lambda Calculus and Combinatory Logic

Abstract

Cite as

Thanks for your feedback!

Could not send message