License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2016.18
URN: urn:nbn:de:0030-drops-59785
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5978/
Go to the corresponding LIPIcs Volume Portal

de Vries, Fer-Jan

On Undefined and Meaningless in Lambda Definability

pdf-format:
LIPIcs-FSCD-2016-18.pdf (0.5 MB)

Abstract

We distinguish between undefined terms as used in lambda definability
of partial recursive functions and meaningless terms as used in
infinite lambda calculus for the infinitary terms models that
generalise the Bohm model. While there are uncountable many known
sets of meaningless terms, there are four known sets of undefined
terms. Two of these four are sets of meaningless terms.

In this paper we first present set of sufficient conditions for a set
of lambda terms to serve as set of undefined terms in lambda
definability of partial functions. The four known sets of undefined
terms satisfy these conditions.

Next we locate the smallest set of meaningless terms satisfying these
conditions. This set sits very low in the lattice of all sets of
meaningless terms. Any larger set of meaningless terms than this
smallest set is a set of undefined terms. Thus we find uncountably
many new sets of undefined terms.

As an unexpected bonus of our careful analysis of lambda definability
we obtain a natural modification, strict lambda-definability, which
allows for a Barendregt style of proof in which the representation of
composition is truly the composition of representations.

BibTeX - Entry

@InProceedings{devries:LIPIcs:2016:5978,
  author =	{Fer-Jan de Vries},
  title =	{{On Undefined and Meaningless in Lambda Definability}},
  booktitle =	{1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-010-1},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{52},
  editor =	{Delia Kesner and Brigitte Pientka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5978},
  URN =		{urn:nbn:de:0030-drops-59785},
  doi =		{10.4230/LIPIcs.FSCD.2016.18},
  annote =	{Keywords: lambda calculus, lambda definability, partial recursive function, undefined term, meaningless term}
}

Keywords: lambda calculus, lambda definability, partial recursive function, undefined term, meaningless term
Collection: 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016)
Issue Date: 2016
Date of publication: 17.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI