Typically in lambda calculus you have an infinite stock of variables. Could we get away with a finite set?
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ If I understand what you mean by "get away with", yes, since only three variables are needed to encode a complete combinator basis such as SKI or BCKW. Conversely, Richard Statman proved that two variables are not enough, as explained in my answer here. $\endgroup$– Noam ZeilbergerAug 29, 2021 at 13:21
-
1$\begingroup$ Good point. That was my intuition about it. Thanks $\endgroup$– Benjamin GrangeAug 29, 2021 at 14:09
Add a comment
|