Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435121 | Theoretical Computer Science | 2011 | 14 Pages |
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