Á. García-Pérez ; P. Nogueira - No solvable lambda-value term left behind

lmcs:1644 - Logical Methods in Computer Science, June 30, 2016, Volume 12, Issue 2 - https://doi.org/10.2168/LMCS-12(2:12)2016
No solvable lambda-value term left behindArticle

Authors: Á. García-Pérez ; P. Nogueira

    In the lambda calculus a term is solvable iff it is operationally relevant. Solvable terms are a superset of the terms that convert to a final result called normal form. Unsolvable terms are operationally irrelevant and can be equated without loss of consistency. There is a definition of solvability for the lambda-value calculus, called v-solvability, but it is not synonymous with operational relevance, some lambda-value normal forms are unsolvable, and unsolvables cannot be consistently equated. We provide a definition of solvability for the lambda-value calculus that does capture operational relevance and such that a consistent proof-theory can be constructed where unsolvables are equated attending to the number of arguments they take (their "order" in the jargon). The intuition is that in lambda-value the different sequentialisations of a computation can be distinguished operationally. We prove a version of the Genericity Lemma stating that unsolvable terms are generic and can be replaced by arbitrary terms of equal or greater order.


    Volume: Volume 12, Issue 2
    Published on: June 30, 2016
    Submitted on: November 19, 2015
    Keywords: Computer Science - Logic in Computer Science,F.4.1

    Classifications

    1 Document citing this article

    Consultation statistics

    This page has been seen 2021 times.
    This article's PDF has been downloaded 934 times.