FANDOM


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 Ξ(n) outgrew Rayo(n) and that it took the place as the fastest-growing function yet defined.

Definition Edit

Skiing

A skier, enjoying himself but likely not concerned with combinatory logic.

SKI calculus Edit

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

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 \(Ω\), 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 Ξ(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 Ξ.

We could add another oracle combinator Ω’ which works like Ω, 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 Ξ, which Goucher denoted Ξ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 Edit

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& 98 \\    \Xi(9) &\geq& 167 \\ \Xi(10) &\geq& 296 \\ \Xi(11) &\geq& 513 \\ \Xi(12) &\geq& 846 \\  \Xi(n) &>& 7F_{n-2} \text{ (for } n\geq 7) \\     \end{eqnarray}

Where \(F_{n-2}\) denotes n-2th member of the Fibonacci sequence.

Stronger bounds have been found by Lawrence Hollom, by constructing the fast-growing hierarchy in SKI calculus.[2] This method is called top-down. This contstruction yielded the following lower bounds to a weaker version of the function, which lacks the \(Ω\) combinator:

\begin{eqnarray} \Xi(37) &\geq& 5f_3(3)+1 \\ \Xi(42) &\geq& 5f_3(4)+1 \\ \Xi(43) &\geq& 5f_{\omega+1}(2)+1 \\ \Xi(48) &\geq& 5f_{\omega+1}(3)+1 \\ \Xi(50) &\geq& 5f_{\omega+2}(2)+1 \\ \Xi(55) &\geq& 5f_{\omega+2}(3)+1 \\ \Xi(57) &\geq& 5f_{\omega+3}(2)+1 \\ \Xi(62) &\geq& 5f_{\omega+3}(3)+1 \\ \Xi(64) &\geq& 5f_{\omega+4}(2)+1 \\ \Xi(68) &\geq& 5f_{\omega2+1}(2)+1 \\    \end{eqnarray}

Where \(f\) refers to the fast-growing hierarchy. Consequently, \(\Xi(50) > G\), where G=Graham's number.

Winning sequences Edit

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)\)Edit

SSS(SI)
S(SI)(S(SI))

\(\Xi(6)\)Edit

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)\)Edit

\(\Xi(7)\) marks the first time the oracle combinator gives the xi function an advantage over standard SKI calculus.

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 higherEdit

The best known combinator for \(\Xi(8)\) is SSS(SI)S(SΩ)

The best known combinator for \(\Xi(9)\) is SSS(SI)S(S(SΩ))

The best known combinator for \(\Xi(10)\) is SSS(SI)S(S(S(SΩ)))

The best known combinator for \(\Xi(11)\) is SSS(SI)S(S(S(S(SΩ))))

The best known combinator for \(\Xi(12)\) is SSS(SI)S(S(S(S(S(SΩ)))))

TreesEdit

XI(6)

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 Edit

  1. Goucher, Adam P. The Ξ function. Retrieved 14.03.2013.
  2. Hollom, Lawrence. Bounding The Xi Function. Retrieved 21.08.2014.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.