Easy lambda-terms are not always simple
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.
- A filter lambda model and the completeness of type assignment
- Algebras and combinators
- An approximation theorem for topological lambda models and the topological incompleteness of lambda calculus
- An extension of basic functionality theory for -calculus
- Easiness in graph models
- Effective λ-models versus recursively enumerable λ-theories
- From computation to foundations via functions and application: The \(\lambda\)-calculus and its webbed models
- Graph models of $\lambda$-calculus at work, and variations
- scientific article; zbMATH DE number 3648679 (Why is no real title available?)
- scientific article; zbMATH DE number 3889502 (Why is no real title available?)
- scientific article; zbMATH DE number 3916224 (Why is no real title available?)
- scientific article; zbMATH DE number 3672266 (Why is no real title available?)
- scientific article; zbMATH DE number 3780545 (Why is no real title available?)
- scientific article; zbMATH DE number 23772 (Why is no real title available?)
- scientific article; zbMATH DE number 3503200 (Why is no real title available?)
- scientific article; zbMATH DE number 3556025 (Why is no real title available?)
- scientific article; zbMATH DE number 3594646 (Why is no real title available?)
- scientific article; zbMATH DE number 2044491 (Why is no real title available?)
- scientific article; zbMATH DE number 937379 (Why is no real title available?)
- Intersection types and domain operators
- Isomorphism and equational equivalence of continuous \(\lambda\)-models
- Models of the lambda calculus
- On the construction of stable models of untyped -calculus
- On the Jacopini technique
- Set-theoretical and other elementary models of the \(\lambda\)-calculus
- Set-theoretical models of lambda-calculus: theories, expansions, isomorphisms
- Simple easy terms
- Some new results on easy lambda-terms
- The lambda calculus. Its syntax and semantics. Rev. ed.
- Topological incompleteness and order incompleteness of the lambda calculus
- What is a model of the lambda calculus?
- Some new results on easy lambda-terms
- Consistency of a -theory with n-tuples and easy term
- Simple easy terms
- Graph easy sets of mute lambda terms
- scientific article; zbMATH DE number 3916224 (Why is no real title available?)
- scientific article; zbMATH DE number 23772 (Why is no real title available?)
- On sets of terms having a given intersection type
- No solvable lambda-value term left behind
This page was built for publication: Easy lambda-terms are not always simple
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2889181)
