Reductions in combinatory logic and Curry's last problem
- LecturerMr. Fan Ho (Department of Philosophy, National Chung Cheng University)
Host: Churn-Jung Liau - Time2026-11-19 (Thu.) 15:30 ~ 16:45
- LocationAuditorium 106 at IIS new Building
Abstract
Combinatory logic and λ-calculus have similar motivation, formation, and technical results. It should be no surprise if they correspond to each other closely. However, the most intuitive relation in combinatory logic, say, weak reduction, is not a proper analogue of well-known relations in λ-calculus, say, β-reduction and βη-reduction.
In their book Combinatory Logic, Volume I (1958), Curry and Feys introduced the notion of strong reduction, or η-strong reduction, which is generated from weak reduction. It is later proved that η-strong reduction corresponds to βη-reduction properly. Curry worked on defining a relation in combinatory logic which is analogous to β-reduction in the rest of his life; but until now, defining such a relation, which we should call β-strong reduction here, is still an open problem. This is what Hindley called Curry’s last problem.
In this talk, I shall review the studies of η-strong reduction and β-strong reduction, discuss the difficulty of defining an ideal β-strong reduction, and provide a solution to Curry’s last problem.
In their book Combinatory Logic, Volume I (1958), Curry and Feys introduced the notion of strong reduction, or η-strong reduction, which is generated from weak reduction. It is later proved that η-strong reduction corresponds to βη-reduction properly. Curry worked on defining a relation in combinatory logic which is analogous to β-reduction in the rest of his life; but until now, defining such a relation, which we should call β-strong reduction here, is still an open problem. This is what Hindley called Curry’s last problem.
In this talk, I shall review the studies of η-strong reduction and β-strong reduction, discuss the difficulty of defining an ideal β-strong reduction, and provide a solution to Curry’s last problem.