<p>It should be noted that finding combinators with certain reduction properties is <em>always</em> 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).</p>

<p>There are several simple open questions of a similar flavor, e.g. problems #4, #6 and #10 from the <a href="http://tlca.di.unito.it/opltlca/" rel="nofollow noreferrer">TLCA list of open problems</a>.</p>

<p>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.</p>

<p><strong>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.</strong></p>

CC BY-SA 3.0
2017-08-10T18:39:35.937Z
Actually, two variables are not enough (http://dl.acm.org/citation.cfm?id=2100917, https://cstheory.stackexchange.com/a/36344/674), so this gives a slightly higher lower bound (size 5 = 3 abstractions and 2 applications).
Noam Zeilberger
CC BY-SA 3.0
2017-08-10T20:42:38.110Z
@NoamZeilberger alright, that's a fantastic result I was not aware of!
cody
CC BY-SA 3.0
2015-07-06T14:56:26.697Z
2017-08-10T20:45:42.877Z
2017-08-10T20:45:42.877Z
cody
<p>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.
<a href="http://arxiv.org/pdf/cs/0508056v1.pdf">http://arxiv.org/pdf/cs/0508056v1.pdf</a></p>

<p>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.</p>

CC BY-SA 3.0
2016-12-15T10:37:09.087Z
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).
2012rcampion
CC BY-SA 3.0
2015-07-06T00:26:19.827Z
2015-07-06T10:07:35.610Z
2015-07-06T10:07:35.610Z
Joshua Herman
<p>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.</p>
<p>Minimal representations of S, K, and I are:</p>
<p>S = A (A (A A (A A (A A))(A (A (A A (A A)))))) A A</p>
<p>K = A (A A) (A (A A) A A A A A)</p>
<p>I = A (A (A (A A) A)) (A (A A) A)</p>

CC BY-SA 4.0
2023-12-23T22:20:17.320Z
Thanks for your answer. Is there a proof that this is the smallest possible size?
user76284
CC BY-SA 4.0
2023-12-24T15:47:32.697Z
Our exhaustive search found all terms of fewer than 26 bits not to provide a basis, but the work is unpublished.
John Tromp
CC BY-SA 4.0
2023-12-24T21:48:11.500Z
Interesting. Do you have an idea of when it will be published?
user76284
CC BY-SA 4.0
2023-12-24T23:31:01.890Z
And are there other universal terms of equal size, or is it unique?
user76284
CC BY-SA 4.0
2023-12-27T15:02:06.930Z
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.
John Tromp
CC BY-SA 4.0
2023-12-23T19:23:07.267Z
2023-12-23T19:23:07.267Z
John Tromp
<p>I am looking for the smallest possible <a href="https://en.wikipedia.org/wiki/Combinatory_logic#One-point_basis" rel="nofollow noreferrer">universal combinator</a>, measured by the number of abstractions and applications required to specify such a combinator in the <a href="https://en.wikipedia.org/wiki/Lambda_calculus#Free_and_bound_variables" rel="nofollow noreferrer">lambda calculus</a>. Examples of universal combinators include:</p>

<ul>
<li><strong>size 23:</strong> λf.f(fS(KKKI))K</li>
<li><strong>size 18:</strong> λf.f(fS(KK))K</li>
<li><strong>size 14:</strong> λf.fKSK</li>
<li><strong>size 12:</strong> λf.fS(λxyz.x)</li>
<li><strong>size 11:</strong> λf.fSK</li>
</ul>

<p>where S = λxyz.xz(yz) of <strong>size 6</strong> and K = λxy.x of <strong>size 2</strong> are the combinators of the <a href="https://en.wikipedia.org/wiki/SKI_combinator_calculus" rel="nofollow noreferrer">SK combinator calculus</a>. The first 4 examples are described in <a href="http://link.springer.com/article/10.1007%2FBF03180572" rel="nofollow noreferrer">this paper</a>.</p>

<p>My questions are:</p>

<ul>
<li>Are there any universal combinators that are smaller in size?</li>
<li>What is the smallest possible universal combinator?</li>
</ul>

<p><strong>EDIT:</strong> See also <a href="https://math.stackexchange.com/a/180263/76284">https://math.stackexchange.com/a/180263/76284</a>, which has <code>λazbc.bc(a(λy.c))</code> (which would be of <strong>size 8</strong>, matching the sum of sizes of the SK basis). Does anyone know how to express S and K from this combinator?</p>

CC BY-SA 3.0
2015-07-02T16:12:29.413Z
Maybe this is of interest: https://www.wolframscience.com/nksonline/page-1123a-text?firstview=1
Andrej Bauer
CC BY-SA 3.0
2015-07-06T10:49:27.170Z
What is your definition of size? Can you write it as a function?
Joshua Herman
CC BY-SA 3.0
2017-08-10T18:48:00.263Z
Since 6 + 2 = 8 < 11, this makes me wonder whether {S,K} is the smallest basis of combinators measured by total size?
Noam Zeilberger
CC BY-SA 3.0
2017-11-15T08:57:43.130Z
Your recent edit rather sounds like a (partial) answer.
Emil Jeřábek
CC BY-SA 3.0
2017-11-16T10:47:47.767Z
How strictly are you defining "*combinator*"? Does it have to be of the form `λx*.E` where `E` is abstraction-free?
Peter Taylor
CC BY-SA 4.0
2021-01-02T06:31:00.967Z
@PeterTaylor [Craig's theorem](https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/a-new-proof-for-craigs-theorem/888D7384A22A933DF532B8F9115EB07F) implies that any universal combinator must be improper.
user76284
CC BY-SA 4.0
2022-10-11T06:34:53.520Z
@JoshuaHerman Here, size = abstractions + applications.
user76284
<lo.logic><computability><lambda-calculus><universal-computation><combinatory-logic>
Smallest possible universal combinator
user76284
# Smallest possible universal combinator

(Asked by: username_0 on 2015-07-01)

I am looking for the smallest possible [universal combinator](https://en.wikipedia.org/wiki/Combinatory_logic#One-point_basis), measured by the number of abstractions and applications required to specify such a combinator in the [lambda calculus](https://en.wikipedia.org/wiki/Lambda_calculus#Free_and_bound_variables). 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](https://en.wikipedia.org/wiki/SKI_combinator_calculus). The first 4 examples are described in [this paper](http://link.springer.com/article/10.1007%2FBF03180572).

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?

**Tags:** lo.logic, computability, lambda-calculus, universal-computation, combinatory-logic

> **Comments:**
> **username_1**: Maybe this is of interest: https://www.wolframscience.com/nksonline/page-1123a-text?firstview=1  
> **username_2**: What is your definition of size? Can you write it as a function?  
> **username_3**: Since 6 + 2 = 8 < 11, this makes me wonder whether {S,K} is the smallest basis of combinators measured by total size?  
> **username_4**: Your recent edit rather sounds like a (partial) answer.  
> **username_5**: How strictly are you defining "*combinator*"? Does it have to be of the form `λx*.E` where `E` is abstraction-free?  
> **username_0**: @PeterTaylor [Craig's theorem](https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/a-new-proof-for-craigs-theorem/888D7384A22A933DF532B8F9115EB07F) implies that any universal combinator must be improper.  
> **username_0**: @JoshuaHerman Here, size = abstractions + applications.  

---

## 3 answers

### Answer by username_6 on 2015-07-06. Score: 10

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](http://tlca.di.unito.it/opltlca/).

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.**

> **Comments:**
> **username_3**: Actually, two variables are not enough (http://dl.acm.org/citation.cfm?id=2100917, https://cstheory.stackexchange.com/a/36344/674), so this gives a slightly higher lower bound (size 5 = 3 abstractions and 2 applications).  
> **username_6**: @NoamZeilberger alright, that's a fantastic result I was not aware of!  

---

### Answer by username_2 on 2015-07-06. Score: 8

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.

> **Comments:**
> **username_7**: 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).  

---

### Answer by username_8 on 2023-12-23. Score: 7

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)

> **Comments:**
> **username_0**: Thanks for your answer. Is there a proof that this is the smallest possible size?  
> **username_8**: Our exhaustive search found all terms of fewer than 26 bits not to provide a basis, but the work is unpublished.  
> **username_0**: Interesting. Do you have an idea of when it will be published?  
> **username_0**: And are there other universal terms of equal size, or is it unique?  
> **username_8**: 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.  

---

