[Next]  [Previous]  [Up]  

Problem # 3 [SOLVED]

Submitted by Richard Statman
Date: 1981
Statement. Does the range property hold for the theory ℋ ?
Problem Origin. The problem was first posed by Henk Barendregt .


Consider the least lambda theory ℋ which equates all unsolvable terms. Take any combinator F  . Prove that either ℋ  ⊢ FM  =  F N  , for all closed M  , N  , or there are infinitely many closed Mi  , such that no two of terms FMi  are equated under ℋ . This problem, known as the range problem for ℋ , is stated as Conjecture 20.2.8 in [Barendregt, 1984].

Comments by Richard Statman: Different researchers have different takes on this problem. Mine are the following.

Solution: A negative solution has been presented by A. Polonsky in 2010 and published in [Polonsky, 2012], who constructs a term F with a two-element range. In contrast, Intrigila and Statman [Intrigila and Statman, 2011] showed that the range property for Combinatory Logic is true.

References for # 3

[Barendregt, 1984]    Barendregt, H. (1984). The Lambda Calculus. Its Syntax and Semantics. North-Holland, second edition.

[Intrigila and Statman, 2011]    Intrigila, B. and Statman, R. (2011). Solution to the range problem for combinatory logic. Fundamenta Informaticae, 111(2):203–222.

[Polonsky, 2012]    Polonsky, A. (2012). The range property fails for H. Journal of Logic and Computation, 77(4):1195–1210.

[Next]  [Previous]  [Up]  
© 2006 Dip. Informatica - Universita di Torino
Last modified: July 21, 2014