Solution to the Range Problem for Combinatory Logic

Article type: Research Article

Authors: Intrigila, Benedetto | Statman, Richard

Affiliations: Dipartimento di Matematica, Università di Roma “Tor Vergata”, Rome, Italy. intrigil@mat.uniroma2.it | Department of Mathematical Sciences, Carnegie-Mellon University, Pittsburgh, PA, USA. rs31@andrew.cmu.edu

Note: [] Address for correspondence: Dipartimento di Matematica, Università di Roma “Tor Vergata”, Rome, Italy

Abstract: The λ-theory ℋ is obtained from β-conversion by identifying all closed unsolvable terms (or, equivalently, terms without head normal form). The range problem for the theory ℋ asks whether a closed term has always (up to equality in ℋ) either an infinite range or a singleton range (that is, it is a constant function). Here we give a solution to a natural version of this problem, giving a positive answer for the theory ℋ restricted to Combinatory Logic. The method of proof applies also to the Lazy λ-Calculus.

Keywords: Lambda-Calculus, Combinatory Logic, Range Problem

DOI: 10.3233/FI-2011-560

Journal: Fundamenta Informaticae, vol. 111, no. 2, pp. 203-222, 2011