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

Sfgx => fx(gx) Kfx => f Ix => x

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.

Busy Beaver for SKI calculus (BB_SKI) is a variation of the Busy Beaver problem for lambda calculus. BB_SKI(n) is defined as the size of the largest output of a terminating program of size n.

Champions

n	Value	Champion	Discovered by
1	= 1	S
2	= 2	SS
3	= 3	SSS
4	= 4	SSSS
5	= 6	SSS(SS)
6	= 17	SSS(SI)S
7	≥ 41	SSS(S(SS))S
8	≥ 80	SSK(S(SS)S)S
9	≥ 169	S(SS)(SS)(SS)SS
10	≥ 376	S(S(SS(KK)))(SS)(SS)
11	≥ 912	S(SS)S(SS)(S(S(KS))S)
12	≥ 196606	S(S(SI))I(S(S(KS)K)I)K
13	> 2^2^2^21	S(S(SSS)I)I(S(S(KS)K)I)
14	> 2^^18	S(S(S(SSS))I)I(S(S(KS)K)I)
15	> 2^^2^128	SSK(S(S(KS)K)I)(S(SSSI)I)
16	> 2^^2^2^2^2^21	SSK(S(S(KS)K)I)(S(S(SSS)I)I)
17	> 2^^^2^128	S(SSK(S(SSSI)I))I(S(S(KS)K)I)
18	> 2^^^2^2^2^2^21	S(SSK(S(S(SSS)I)I))I(S(S(KS)K)I))
19	> 2^^^2^^19	S(SSK(S(S(S(SSS))I)I))I(S(S(KS)K)I)
20	> 3{{1}}(2^^7/2-1)	S(S(S(SI)))I(S(K(S(SS(K(K(S(S(KS)K)I))))))K)

SK calculus

We can remove the I combinator and replace it by (SKS), (SKK) or any (SKx). These terms have a straightforward binary encoding where (prefix) application is 1, K=00, and S=01. Since n combinators take n-1 applications to combine, their code length is 2n + n-1 = 3n-1 bits.

Champions

n	bits	Value	Champion	Discovered 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	≥ 41	SSS(S(SS))S
8	23	≥ 80	SSK(S(SS)S)S
9	26	≥ 169	S(SS)(SS)(SS)SS
10	29	≥ 376	S(S(SS(KK)))(SS)(SS)
11	32	≥ 912	S(SS)S(SS)(S(S(KS))S)
12	35	≥ 913	S(S(SS)S(SS)(S(S(KS))S))
13	38	≥ 914	S(S(S(SS)S(SS)(S(S(KS))S)))
14	41	≥ 1530	SS(SKK)(SS)(SS(SS(SS)))S
15	44	≥ 7811	SS(SKK)(SS)(SS(SS(SSS)))S

TODO: Champions analysis.

BCKW system

BCKW system is a variation of SK calculus that replace the S combinator by 3 other simpler combinators.

Bfgx => f(gx) Cfxy => fyx Kfx => f Wfx => fxx

Champions

n	Value	Champion	Discovered by
1	= 1	B
2	= 2	BB
3	= 3	BBB
4	≥ 11	WW(WB)
5	≥ 47	W(WW)(WB)
6	≥ 3*2^66-1	WB(WW)(WB)
7	> 2^2^2^20	WB(W(WW))(WB)
8	> 2^^17	WC(WW(WB))(WW)
9	> 2^^2^2^65	WB(C(WC))(WW)(WB)
10	> 2^^2^2^2^2^20	WB(C(WC))(W(WW))(WB)
11	> f_ω 2^2^18	WB(W(C(WC)(C(WC))))(WB)
12	> f_ω+1 (2^2^18-2)	W(WC(W(C(WC)(C(WC)))))(WB)

Oracles

We can extend BB_SKI with oracles, making it stronger than BB. For example, we can add an oracle combinator O where Ofxy=x iff for all z fz=z, and y otherwise. The resulting busy beaver, known as the Xi function, is estimated to be faster-growing than ordinal oracle busy beavers with the oracle degree <= w_1^CK. A further extension would be to add another oracle, O’, where O’fxy=x iff f is well-founded, and y otherwise, where a term is well-founded iff there is no infinitely nested outermost-redex oracle calls. The resulting busy beaver is called Xi_2.

See Also

• Lower bounds of this function (archived)
• SKI interpreter
• Brainfuck