The search for a reduction in combinatory logic equivalent to λβ-reduction

被引:2
|
作者
Seldin, Jonathan P. [1 ]
机构
[1] Univ Lethbridge, Dept Math & Comp Sci, Lethbridge, AB T1K 3M4, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
lambda-calculus; Combinatory logic; beta-reduction; beta eta-reduction; Abstraction; Irreducible terms; Normal form; FUNDAMENTAL PRINCIPLES; FOUNDATION; SET;
D O I
10.1016/j.tcs.2011.02.002
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Combinatory logic (CL) is generally regarded as equivalent to lambda-calculus (lambda.), and in most respects, it is. However, with respect to reduction, the equivalence is not complete. In CL, there is not, as yet, a reduction relation which is generally accepted as an equivalent to lambda beta-reduction in A. There are some proposals for such a reduction, but so far none of them has as yet a complete syntactically useful characterization of the irreducible CL-terms. This paper is about the search for a reduction on CL equivalent to lambda beta-reduction. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:4905 / 4918
页数:14
相关论文
共 50 条