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))K
- size 18: λf.f(fS(KK))K
- size 14: λf.fKSK
- size 12: λf.fS(λxyz.x)
- size 11: λf.fSK
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)) (which would be of size 8, matching the sum of sizes of the SK basis). Does anyone know how to express S and K from this combinator?