Article ID Journal Published Year Pages File Type
435121 Theoretical Computer Science 2011 14 Pages PDF
Abstract

Combinatory logic (CL) is generally regarded as equivalent to λ-calculus (λ), 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 λβ-reduction in λ. 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 λβ-reduction.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics