Busy Beaver for SKI calculus
Busy Beaver for SKI calculus (we will call it BBSKI for now) is a variation of the Busy Beaver problem for lambda calculus.
A SKI calculus program is a binary tree where the leaves are combinators, the three symbols S, K, I. Using parentheses to notate the tree, a simple example of a SKI program is (((SK)S)((KI)S)). We can omit parentheses by assuming they are left-binding by default, so we simplify our program to SKS(KIS).
Like lambda calculus, SKI calculus has a process called beta-reduction. We change the tree according to the leftmost combinator.
Ix -> IKxy -> KxSxyz -> Sxz(yz)
Note that xyz represent any valid trees, not just single combinators.
We repeat this process and we say it terminates if the combinator cannot be beta-reduced.
Champions
| n | Value | Champion | Discoverered by |
|---|---|---|---|
| 1 | = 1 | S | ? |
| 2 | = 2 | SS | ? |
| 3 | = 3 | SSS | ? |
| 4 | = 4 | SSSS | ? |
| 5 | = 6 | SSS(SS) | ? |
| 6 | = 17 | SSS(SI)S | ? |
| 7 | ≥ 18 | S(SSS(SI)S) | ? |
| 8 | ≥ 19 | SS(SSS(SI)S) | ? |
| 9 | ≥ 519 | SSI((S(SS)S)S)K | ? |
| 10 | ≥ 1041 | SSI((S(SS)S)S)KS | ? |
SK calculus
We can remove the I combinator and replace it by (SKS), (SKK) or any (SKx).
Champions
| n | Value | Champion | Discoverered by |
|---|---|---|---|
| 1 | = 1 | S | ? |
| 2 | = 2 | SS | ? |
| 3 | = 3 | SSS | ? |
| 4 | = 4 | SSSS |
? |
| 5 | = 6 | SSS(SS) |
? |
| 6 | ≥ 8 | SSS(SSS) |
? |
| 7 | ≥ 10 | SSS(SSSS)
|
? |
| 8 | ≥ 23 | SSS(S(SKS))S
|
? |