Curry's Last Problem: Imitating Lambda-beta-reduction in Combinatory Logic

Roger Hindley
University of Wales Swansea

The last problem on which Curry worked before he died in 1982 was that of defining a reduction in combinatory logic to correspond closely to the usual beta-reduction in lambda-calculus. He did not succeed. Several solutions to this problem have been posed since then, but  despite some ingenuity in their formulation, none has been really clean and simple enough to make its development attractive. I believe the task of finding a workable combinatory beta-reduction is one of the main unsolved problems in combinatory logic. (It is not a "tidy" problem and it promises no beautiful solution -- but then, neither does real life!)  In this talk I shall discuss criteria for acceptability of a beta reduction, and describe the known candidates, and suggest how far they succeed or fail in satisfying these.