17
$\begingroup$

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

where 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)) (which would be of size 8, matching the sum of sizes of the SK basis).

$\endgroup$
  • $\begingroup$ Maybe this is of interest: wolframscience.com/nksonline/page-1123a-text?firstview=1 $\endgroup$ – Andrej Bauer Jul 2 '15 at 16:12
  • $\begingroup$ What is your definition of size? Can you write it as a function? $\endgroup$ – Joshua Herman Jul 6 '15 at 10:49
  • $\begingroup$ Since 6 + 2 = 8 < 11, this makes me wonder whether {S,K} is the smallest basis of combinators measured by total size? $\endgroup$ – Noam Zeilberger Aug 10 '17 at 18:48
  • $\begingroup$ Your recent edit rather sounds like a (partial) answer. $\endgroup$ – Emil Jeřábek Nov 15 '17 at 8:57
  • $\begingroup$ How strictly are you defining "combinator"? Does it have to be of the form λx*.E where E is abstraction-free? $\endgroup$ – Peter Taylor Nov 16 '17 at 10:47
9
$\begingroup$

It should be noted that finding combinators with certain reduction properties is always difficult, and finding the smallest such combinator may easily be undecidable (for trivial reasons, as it may be undecidable to prove that a certain application of the combinator even halts).

There are several simple open questions of a similar flavor, e.g. problems #4, #6 and #10 from the TLCA list of open problems.

One thing to note is that your combinator certainly needs to have at least 2 bound variables, one of which is duplicated (as does any complete set of combinators) and one needs to be erased. This puts a lower bound of 4, I think (2 abstractions and 2 appearances of a variable), which is not so far from the upper bound of 11.

Edit: Noam's comments and reference push the lower bound to 5! I wouldn't be surprised if the proof also requires the extra variable to appear as well, which would push us to 6.

$\endgroup$
7
$\begingroup$

For your first question I believe this paper may help a bunch. It has a 6 bit combinator calculus that is also an UTM. Also it has a universal combinator that seems to have size 7 with one element given what you want. They call it Zot. http://arxiv.org/pdf/cs/0508056v1.pdf

I am not sure if you can say or prove that there is a minimal combinator. The paper would suggest it would have to be at least be less than 6 bits.

$\endgroup$
  • 2
    $\begingroup$ Zot's combinator is actually the last one listed in the OP: λx.xSK (shared with its parent languages, Iota and Jot), which has length 11. In the "6 bit combinator calculus" (Keraia), the "6 bits" is the size of the UTM; and it looks like it's just an encoding of the lambda calculus, not a combinator calculus (and therefore doesn't have a builtin universal combinator). $\endgroup$ – 2012rcampion Dec 15 '16 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.