21
$\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). Does anyone know how to express S and K from this combinator?

Improve this question
$\endgroup$
7
  • $\begingroup$ Maybe this is of interest: wolframscience.com/nksonline/page-1123a-text?firstview=1 $\endgroup$
    – Andrej Bauer
    Commented Jul 2, 2015 at 16:12
  • $\begingroup$ What is your definition of size? Can you write it as a function? $\endgroup$
    – Joshua Herman
    Commented Jul 6, 2015 at 10:49
  • 1
    $\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
    Commented Aug 10, 2017 at 18:48
  • $\begingroup$ Your recent edit rather sounds like a (partial) answer. $\endgroup$
    – Emil Jeřábek
    Commented Nov 15, 2017 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
    Commented Nov 16, 2017 at 10:47

3 Answers 3

Reset to default
10
$\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.

Improve this answer
$\endgroup$
2
8
$\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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Dec 15, 2016 at 10:37
7
$\begingroup$

The smallest basis is the single point combinator A = λx λy λz. x z (y (λ_.z)) of size 4 abstractions + 3 applications, and of minimal size 26 bits in the binary lambda calculus.

Minimal representations of S, K, and I are:

S = A (A (A A (A A (A A))(A (A (A A (A A)))))) A A

K = A (A A) (A (A A) A A A A A)

I = A (A (A (A A) A)) (A (A A) A)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your answer. Is there a proof that this is the smallest possible size? $\endgroup$
    – user76284
    Commented Dec 23, 2023 at 22:20
  • $\begingroup$ Our exhaustive search found all terms of fewer than 26 bits not to provide a basis, but the work is unpublished. $\endgroup$
    – John Tromp
    Commented Dec 24, 2023 at 15:47
  • 1
    $\begingroup$ Interesting. Do you have an idea of when it will be published? $\endgroup$
    – user76284
    Commented Dec 24, 2023 at 21:48
  • $\begingroup$ And are there other universal terms of equal size, or is it unique? $\endgroup$
    – user76284
    Commented Dec 24, 2023 at 23:31
  • $\begingroup$ There are 2 more minimal (26 bit) universal ones: λx λy λz. y z (x (λ_.z)) and x λy λz. y (λ_.z) (x z), although they require longer expressions for S and K. $\endgroup$
    – John Tromp
    Commented Dec 27, 2023 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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