SKI Calculus: Difference between revisions
→Champions: new bounds |
n S/K combinators take 3n-1 bits to encode in Binary Combinatory Logic |
||
| Line 112: | Line 112: | ||
=== Champions === | === Champions === | ||
{| class="wikitable" | {| class="wikitable" | ||
! n !! Value !! Champion !! Discoverered by | ! n !! bits !! Value !! Champion !! Discoverered by | ||
|- | |- | ||
| 1 || = 1 || S || ? | | 1 || 2 || = 1 || S || ? | ||
|- | |- | ||
| 2 || = 2 || SS || ? | | 2 || 5 || = 2 || SS || ? | ||
|- | |- | ||
| 3 || = 3 || SSS || ? | | 3 || 8 || = 3 || SSS || ? | ||
|- | |- | ||
| 4 || = 4 || SSSS || ? | | 4 || 11 || = 4 || SSSS || ? | ||
|- | |- | ||
| 5 || = 6 || SSS(SS) || ? | | 5 || 14 || = 6 || SSS(SS) || ? | ||
|- | |- | ||
| 6 || ≥ 10 || SSS(SS)S || ? | | 6 || 17 || ≥ 10 || SSS(SS)S || ? | ||
|- | |- | ||
|7 | |7 | ||
| 20 | |||
|≥ 40 | |≥ 40 | ||
|S(SS)S(SS)S | |S(SS)S(SS)S | ||
| Line 132: | Line 133: | ||
|- | |- | ||
|8 | |8 | ||
| 23 | |||
|≥ 41 | |≥ 41 | ||
|S(S(SS)S(SS)S) | |S(S(SS)S(SS)S) | ||
| Line 137: | Line 139: | ||
|- | |- | ||
|9 | |9 | ||
| 26 | |||
|≥ 42 | |≥ 42 | ||
|S(S(S(SS)S(SS)S)) | |S(S(S(SS)S(SS)S)) | ||
| Line 142: | Line 145: | ||
|- | |- | ||
|10 | |10 | ||
| 29 | |||
|≥ 66 | |≥ 66 | ||
|SS(SSS)(SS(SS))S | |SS(SSS)(SS(SS))S | ||
| Line 147: | Line 151: | ||
|- | |- | ||
|11 | |11 | ||
| 32 | |||
|≥ 79 | |≥ 79 | ||
|SS(SSS)(SS(SSS))S | |SS(SSS)(SS(SSS))S | ||
| Line 152: | Line 157: | ||
|- | |- | ||
|12 | |12 | ||
| 35 | |||
|≥ 164 | |≥ 164 | ||
|SS(SKK)(SS)(SS(SS))S | |SS(SKK)(SS)(SS(SS))S | ||
| Line 157: | Line 163: | ||
|- | |- | ||
|13 | |13 | ||
| 38 | |||
|≥ 681 | |≥ 681 | ||
|SS(SKK)(SS)(SS(SSS))S | |SS(SKK)(SS)(SS(SSS))S | ||
| Line 162: | Line 169: | ||
|- | |- | ||
|14 | |14 | ||
| 41 | |||
|≥ 1530 | |≥ 1530 | ||
|SS(SKK)(SS)(SS(SS(SS)))S | |SS(SKK)(SS)(SS(SS(SS)))S | ||
| Line 167: | Line 175: | ||
|- | |- | ||
|15 | |15 | ||
| 44 | |||
|≥ 7811 | |≥ 7811 | ||
|SS(SKK)(SS)(SS(SS(SSS)))S | |SS(SKK)(SS)(SS(SS(SSS)))S | ||
Revision as of 08:42, 7 May 2026
Busy Beaver for SKI calculus (we will call it BB_SKI 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 any reducible redex.
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.
BB_SKI(n) is defined as the size of the largest output of a terminating program of size n.
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 | ≥ 40 | S(SS)S(SS)S | ? |
| 8 | ≥ 41 | SII(S(S(SS)))S | ? |
| 9 | ≥ 79 | SII(SS(SSS))S | ? |
| 10 | ≥ 164 | SII(SS(SS(SS)))S | ? |
| 11 | ≥ 681 | SII(SS(SS(SSS)))S | ? |
| 12 | ≥ 1530 | SII(SS(SS(SS(SS))))S | ? |
| 13 | ≥ 65537 | S(S(SI))I(S(S(KS)K)I)KK | ? |
| 14 | ≥ 2^256+1 | S(S(S(SI)))I(S(S(KS)K)I)KK | ? |
| 15 | > 2^2^2^2^21 | S(S(SSS)I)I(S(S(KS)K)I)KK | ? |
| 16 | > 2^^19 | S(S(S(SSS))I)I(S(S(KS)K)I)KK | ? |
| 17 | > 2^^2^128 | SSK(S(S(KS)K)I)(S(SI(SI))I)KK | ? |
| 18 | > 2^^2^2^2^2^21 | SSK(S(S(KS)K)I)(S(S(SSS)I)I)KK | ? |
| 19 | > 2^^^2^128 | S(SSK(S(SI(SI))I))I(S(S(KS)K)I)KK | ? |
| 20 | > 2^^^2^2^2^2^21 | S(SSK(S(S(SSS)I)I))I(S(S(KS)K)I)KK | ? |
| 21 | > 2^^^2^^19 | S(SSK(S(S(S(SSS))I)I))I(S(S(KS)K)I)KK | ? |
SK calculus
We can remove the I combinator and replace it by (SKS), (SKK) or any (SKx).
Champions
| n | bits | Value | Champion | Discoverered by |
|---|---|---|---|---|
| 1 | 2 | = 1 | S | ? |
| 2 | 5 | = 2 | SS | ? |
| 3 | 8 | = 3 | SSS | ? |
| 4 | 11 | = 4 | SSSS | ? |
| 5 | 14 | = 6 | SSS(SS) | ? |
| 6 | 17 | ≥ 10 | SSS(SS)S | ? |
| 7 | 20 | ≥ 40 | S(SS)S(SS)S | ? |
| 8 | 23 | ≥ 41 | S(S(SS)S(SS)S) | ? |
| 9 | 26 | ≥ 42 | S(S(S(SS)S(SS)S)) | ? |
| 10 | 29 | ≥ 66 | SS(SSS)(SS(SS))S | ? |
| 11 | 32 | ≥ 79 | SS(SSS)(SS(SSS))S | ? |
| 12 | 35 | ≥ 164 | SS(SKK)(SS)(SS(SS))S | ? |
| 13 | 38 | ≥ 681 | SS(SKK)(SS)(SS(SSS))S | ? |
| 14 | 41 | ≥ 1530 | SS(SKK)(SS)(SS(SS(SS)))S | ? |
| 15 | 44 | ≥ 7811 | SS(SKK)(SS)(SS(SS(SSS)))S | ? |
See Also
Lower bounds of this function (archived)