Easy lambda-terms are not always simple
type: Item
instance of: scholarly article
title: Easy lambda-terms are not always simple
zbMATH Open document ID: 1253.03035
publication date: 2012-06-04T00:00:00Z
full work available at URL: https://eudml.org/doc/222014
full work available at URL: http://hdl.handle.net/10278/36003
Mathematics Subject Classification ID: 03B40
zbMATH DE Number: 6042921
zbMATH Keywords: lambda calculus
zbMATH Keywords: easy lambda terms
zbMATH Keywords: simple easy lambda terms
zbMATH Keywords: filter models
zbMATH Keywords: ris models
author: Alberto Carraro
author: Antonino Salibra
MaRDI profile type: Publication
OpenAlex ID: W1980508492
cites work: Simple easy terms
cites work: Q4448355
cites work: Intersection types and domain operators
cites work: Q3206926
cites work: The lambda calculus. Its syntax and semantics. Rev. ed.
cites work: A filter lambda model and the completeness of type assignment
cites work: Q4896520
cites work: Some new results on easy lambda-terms
cites work: From computation to foundations via functions and application: The \(\lambda\)-calculus and its webbed models
cites work: Graph models of $\lambda$-calculus at work, and variations
cites work: Easiness in graph models
cites work: Effective λ-models versus recursively enumerable λ-theories
cites work: Q4160405
cites work: An extension of basic functionality theory for \(\lambda\)-calculus
cites work: Q3221961
cites work: Algebras and combinators
cites work: An approximation theorem for topological lambda models and the topological incompleteness of lambda calculus
cites work: Q3982064
cites work: Q4128535
cites work: Q3869319
cites work: Q3691635
cites work: Isomorphism and equational equivalence of continuous \(\lambda\)-models
cites work: On the construction of stable models of untyped \(\lambda\)-calculus
cites work: Models of the lambda calculus
cites work: On the Jacopini technique
cites work: Set-theoretical models of lambda-calculus: theories, expansions, isomorphisms
cites work: What is a model of the lambda calculus?
cites work: Set-theoretical and other elementary models of the \(\lambda\)-calculus
cites work: Topological incompleteness and order incompleteness of the lambda calculus
cites work: Q4083399
cites work: Q3959414
DOI: 10.1051/ITA/2012005
published in: RAIRO. Theoretical Informatics and Applications
review text: A closed lambda term \(M\) is said to be easy if, for any other closed term \(N\), the lambda theory generated by \(M = N\) is consistent. Simple easiness has a rather technical definition. Roughly, as the authors say, \(M\) is simply easy if, for every lambda term \(N\), there is an easy intersection type system which generates a filter model satisfying \(M = N\). Simple easiness, known to imply easiness, also allows the proof of consistency results. This paper solves Problem 19 of the TLCA list in proving that easiness does not imply simple easiness. In fact, the authors provide a non-empty co-r.e. set of easy, but not simply easy, lambda terms.
reviewed by: Martin W. Bunder
description: scientific article; zbMATH DE number 6042921