Busy Beaver for SKI calculus: Difference between revisions
Added SK calculus section. |
used proper greater/equals sign |
||
| Line 30: | Line 30: | ||
|- | |- | ||
|7 | |7 | ||
| | |≥ 18 | ||
|S(SSS(SI)S) | |S(SSS(SI)S) | ||
|? | |? | ||
|- | |- | ||
|8 | |8 | ||
| | |≥ 19 | ||
|SS(SSS(SI)S) | |SS(SSS(SI)S) | ||
|? | |? | ||
|- | |- | ||
|9 | |9 | ||
| | |≥ 519 | ||
|SSI((S(SS)S)S)K | |SSI((S(SS)S)S)K | ||
|? | |? | ||
|- | |- | ||
|10 | |10 | ||
| | |≥ 1041 | ||
|SSI((S(SS)S)S)KS | |SSI((S(SS)S)S)KS | ||
|? | |? | ||
| Line 67: | Line 67: | ||
| 5 || = 6 || <code>SSS(SS)</code> || ? | | 5 || = 6 || <code>SSS(SS)</code> || ? | ||
|- | |- | ||
| 6 || | | 6 || ≥ 8 || <code>SSS(SSS)</code> || ? | ||
|- | |- | ||
|7 | |7 | ||
| | |≥ 10 | ||
|<code>SSS(SSSS)</code> | |<code>SSS(SSSS)</code> | ||
|? | |? | ||
|- | |- | ||
|8 | |8 | ||
| | |≥ 23 | ||
|<code>SSS(S(SKS))S</code> | |<code>SSS(S(SKS))S</code> | ||
|? | |? | ||
Latest revision as of 13:21, 25 December 2025
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
|
? |