Solution to the Range Problem for Combinatory Logic

被引：1

作者：

Intrigila, Benedetto ^{[1
]}

Statman, Richard ^{[2
]}

机构：

[1] Univ Roma Tor Vergata, Dipartimento Matemat, I-00133 Rome, Italy

[2] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

FUNDAMENTA INFORMATICAE | 2011年 / 111卷 / 02期

关键词：

Lambda-Calculus; Combinatory Logic; Range Problem;

D O I：

10.3233/FI-2011-560

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The lambda-theory H is obtained from beta-conversion by identifying all closed unsolvable terms (or, equivalently, terms without head normal form). The range problem for the theory H asks whether a closed term has always (up to equality in H) 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 H restricted to Combinatory Logic. The method of proof applies also to the Lazy lambda-Calculus.

引用

页码：203 / 222

页数：20

共 9 条

[1]

Abramsky S., 1990, LAZY LAMBDA CALCULUS, P65

[2] CONSTRUCTIVE PROOFS OF THE RANGE PROPERTY IN LAMBDA-CALCULUS [J].

BARENDREGT, H .

THEORETICAL COMPUTER SCIENCE, 1993, 121 (1-2) :59-69

[3]

Barendregt H. P., 1984, LAMBDA CALCULUS ITS

[4]

Bezem M., 2003, Cambridge Tracts in Theoretical Computer Science

[5]

Curry H.B., 1972, Combinatory Logic, VII

[6]

Hindley J. R., 1972, INTRO COMBINATORY LO

[7]

Intrigila Benedetto, 2007, REFLECTIONS TYPE THE

[8]

Rogers Hartley, 1987, Theory of Recursive Functions and Effective Computability

[9]

*TLCA, TLCA LIST OP PROBL

← 1 →