- Not to be confused with Rathjen's Ξ function.
The xi function is an uncomputable googological function defined by Adam P. Goucher, based on a variant of SKI combinator calculus[1]. It is one of the fastest-growing functions ever defined, and it is significantly more powerful than Rado's sigma function. Goucher mistakenly claimed that \(\Xi(n)\) outgrew Rayo(n) and that it took the place as the fastest-growing function yet defined.
Definition[]
A skier, enjoying himself but likely not concerned with combinatory logic.
SKI calculus[]
SKI calculus is a subsystem of combinatory logic, itself a precursor of 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, here denoted with \(\Rightarrow\). We take the leftmost combinator and reduce the tree according to the following rules (where):
- \(\mathbf{I}x \Rightarrow x\)
- \(\mathbf{K}xy \Rightarrow x\)
- \(\mathbf{S}xyz \Rightarrow xz(yz)\)
A few clarifications are necessary for these rules. Here, \(x,y,z\) represent any valid trees, not just single combinators. These rules apply to the leftmost part of the tree, so any remaining combinators are left untouched by these transformations.
We repeat this process, and we say that beta-reduction terminates if we reach a point where none of the three above cases apply (for example, if we reach something of the form Kx). Some SKI expressions beta-reduce to a single I, some reduce to another small expression, while others keep on growing forever. If a SKI expression beta-reduces to a string consisting of n combinators, we say that it has output of size n.
As an example, we apply beta-reduction to SKS(KIS): SKS(KIS) => K(KIS)(S(KIS)) => KIS => I.
SKIΩ calculus[]
SKI calculus alone is no more powerful than a Turing machine (in fact, they have the same computational power). But we can greatly increase its strength by adding an additional symbol \(\Omega\), the oracle combinator:
- \(Ωxyz \Rightarrow y\) if \(x\) \(β\)-reduces to \(\mathbf{I}\), and \(Ωxyz \Rightarrow z\) otherwise.
If we start with a string of n symbols and we beta-reduce it, the largest possible finite output is called \(\Xi(n)\). It is possible for a SKIΩ calculus statement to be paradoxical (it can turn out to ask about its own halting, leading to situations like a combinator halting iff it does not halt), and such statements are ignored in the computation of \(\Xi\).
We could add another oracle combinator \(\Omega '\) which works like \(\Omega\), except that it can check if a SKIΩ formula is well-founded (i.e. does not create any kind of paradox). Using this new combinator, we can make a variant of \(\Xi\), which Goucher denoted \(\Xi_2\), which grows even faster than the ordinary xi function. It is possible to continue this further, in analogy to levels of oracle Turing machines.
Values[]
Some exact values and bounds are shown below:
\(\begin{eqnarray} \Xi(1) &=& 1 \\ \Xi(2) &=& 2 \\ \Xi(3) &=& 3 \\ \Xi(4) &=& 4 \\ \Xi(5) &=& 6 \\ \Xi(6) &=& 17 \\ \Xi(7) &=& 51 \\ \Xi(8) &\geq& 137 \\ \Xi(9) &\geq& 519 \\ \Xi(10) &\geq& 1,041 \\ \Xi(11) &\geq& 2,085 \\ \Xi(12) &\geq& 4,173 \\ \Xi(n) &>& 261×2^{n-8}-3 \text{ (for } n\geq 9) \\ \end{eqnarray}\)
Stronger bounds have been found by Lawrence Hollom, later improved by Komi Amiko, by constructing the fast-growing hierarchy in SKI calculus.[2][3] This method is called top-down. This construction yielded the following lower bounds to a weaker version of the function, which lacks the \(Ω\) combinator:
\(\begin{eqnarray} \Xi(16) &\geq& 2^{2^9}+1 > f_3(2) \\ \Xi(21) &>& f_4(2) \\ \Xi(25) &>& f_{\omega+1}(2) \\ \Xi(38) &>& f_{\omega^2+1}(2) \\ \Xi(56) &>& f_{\omega^\omega+1}(2) \\ \Xi(117) &>& f_{\omega^{\omega^\omega}+1}(2) \\ \Xi(2120) &>& f_{\varepsilon_0}(5) \\ \Xi(2123) &>& f_{\varepsilon_0+1}(3) \\ \Xi(2171) &>& f_{\varepsilon_0\omega+1}(3) = f_{\omega^{\varepsilon_0+1}+1}(3) \\ \end{eqnarray}\)
Where \(f\) refers to the fast-growing hierarchy. Additionally, \(\Xi(30) > f_{\omega+2}(2) > G\), where G=Graham's number.
Winning sequences[]
Below is the list of beta-reductions of the expressions that will have maximal length. For \(\Xi(1),\Xi(2),\Xi(3)\) and \(\Xi(4)\) the process is trivial: they are S, S(S), S(SS) and S(SSS) respectively. From \(5 \leq n \leq 7\), it goes as follows:
\(\Xi(5)\)[]
SSS(SI) S(SI)(S(SI))
\(\Xi(6)\)[]
SSS(SI)S S(SI)(S(SI))S SIS(S(SI)S) I(S(SI)S)(S(S(SI)S)) S(SI)S(S(S(SI)S)) SI(S(S(SI)S))(S(S(S(SI)S))) I(S(S(S(SI)S)))(S(S(SI)S)(S(S(S(SI)S)))) S(S(S(SI)S))(S(S(SI)S)(S(S(S(SI)S))))
\(\Xi(7)\)[]
\(\Xi(7)\) marks the first time the oracle combinator gives the xi function an advantage over standard SKI calculus. Also, this is the largest exactly known value of xi function.
SSS(SI)SΩ S(SI)(S(SI))SΩ SIS(S(SI)S)Ω I(S(SI)S)(S(S(SI)S))Ω S(SI)S(S(S(SI)S))Ω SI(S(S(SI)S))(S(S(S(SI)S)))Ω I(S(S(S(SI)S)))(S(S(SI)S)(S(S(S(SI)S))))Ω S(S(S(SI)S))(S(S(SI)S)(S(S(S(SI)S))))Ω S(S(SI)S)Ω(S(S(SI)S)(S(S(S(SI)S)))Ω) S(SI)S(S(S(SI)S)(S(S(S(SI)S)))Ω)(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω)) SI(S(S(SI)S)(S(S(S(SI)S)))Ω)(S(S(S(SI)S)(S(S(S(SI)S)))Ω))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω)) I(S(S(S(SI)S)(S(S(S(SI)S)))Ω))(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω)))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω)) S(S(S(SI)S)(S(S(S(SI)S)))Ω)(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω)))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω)) S(S(SI)S)(S(S(S(SI)S)))Ω(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω)))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))) S(SI)SΩ(S(S(S(SI)S))Ω)(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω)))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))) SIΩ(SΩ)(S(S(S(SI)S))Ω)(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω)))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))) I(SΩ)(Ω(SΩ))(S(S(S(SI)S))Ω)(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω)))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))) SΩ(Ω(SΩ))(S(S(S(SI)S))Ω)(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω)))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))) Ω(S(S(S(SI)S))Ω)(Ω(SΩ)(S(S(S(SI)S))Ω))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω))) Ω(S(S(SI)S)(S(S(S(SI)S)))Ω)(S(S(SI)S)(S(S(S(SI)S)))Ω(S(S(S(SI)S)(S(S(S(SI)S)))Ω))(Ω(S(S(SI)S)(S(S(S(SI)S)))Ω)))
\(\Xi(8)\) and higher[]
- The best known combinator for \(\Xi(8)\) is SSK(S(SSΩ))S
- The best known combinator for \(\Xi(9)\) is SSI((S(SS)S)S)K
- The best known combinator for \(\Xi(10)\) is SSI((S(SS)S)S)KS
- The best known combinator for \(\Xi(11)\) is SSI((S(SS)S)S)KKS
- The best known combinator for \(\Xi(12)\) is SSI((S(SS)S)S)KKKS
Trees[]
.jpg){kind=link}
The trees of the sequence of \(\Xi(6)\)
A common way to write combinators in a more visual way is by using binary trees. S, K, I combinators are identified with leaves. First argument is then the other child of combinator's parent, second argument is the other child of its grandparent and similarly for third argument.
On the right can be seen the sequence of combinators resulting from \(\beta\)-reduction of SSS(SI)S.
Sources[]
- ↑ Goucher, Adam P. The Ξ function. Retrieved 2013-03-14.
- ↑ Hollom, Lawrence. Bounding The Xi Function. Retrieved 2014-08-21.
- ↑ Amiko, Komi. Large numbers in the SKI combinator calculus. Retrieved 2020-07-20.
Bignum Bakeoff contestants: pete-3.c · pete-9.c · pete-8.c · harper.c · ioannis.c · chan-2.c · chan-3.c · pete-4.c · chan.c · pete-5.c · pete-6.c · pete-7.c · marxen.c · loader.c
Channel systems: lossy channel system · priority channel system
Concepts: Recursion
Busy beaver numbers (based on Turing theories): \(\Sigma(1919)\) (1919th busy beaver number) · Fish number 4 · \(\Xi(10^6)\) · \(\Sigma_{\infty}(10^9)\)
Rayo's numbers (based on Set theories): Rayo's number (Rayo(10100)) · Fish number 7 · BIG FOOT (FOOT10(10100)) · Little Bigeddon · Sasquatch · Large Number Garden Number
Miscellany: Hollom's number · Oblivion · Utter Oblivion · (Ultimate Oblivion) · (Hyper oblivion) · (Ultra Oblivion)