I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal combinators include:size 23: f.f(fS(KKKI))Ksize 18: f.f(fS(KK))Ksize 14: f.fKSKsize 12: f.fS(xyz.x)size 11: f.fSKwhere S = xyz.xz(yz) of size 6 and K = xy.x of size 2 are the combinators of the SK combinator calculus. The first 4 examples are described in this paper.My questions are:Are there any universal combinators that are smaller in size?What is the smallest possible universal combinator?EDIT: See also https://math.stackexchange.com/a/180263/76284, which has azbc.bc(a(y.c)).
Smallest possible universal combinator
lo.logic;computability;lambda calculus;universal computation;combinatory logic