Ξ函数

Ξ函数是Adam P. Goucher定义的一个快速增长的不可计算函数。它的“增长率”被估算为OFP。

定义

SKI演算

Ξ函数的定义基于SKI演算，SKI演算是组合逻辑的一个子系统，它是$\lambda$演算的前身。SKI演算是一颗二叉树，其中叶子是组合子为三个符号S、K、I，它们使用括号来表示树。SKI程序的一个简单的例子是$(((SK)S)((KI)S))$.我们默认它们是左结合的。因此可以将其简化为$SKS(KIS)$.

与 $\lambda$演算一样，SKI演算也有一个称为β约化的过程，这里用$\Rightarrow$表示。我们采用左组合的方式，并根据以下规则对树进行约化：

1. $\mathbf{𝐈}x\Rightarrow x$
2. $\mathbf{𝐊}xy\Rightarrow x$
3. $\mathbf{𝐒}xyz\Rightarrow xz(yz)$

这些规则需要进行一些澄清。这里x,y,z表示任何有效的树，而不仅仅是单个符号。这些规则适用于树的最左侧部分，因此任何剩余的符号都不会受到这些转换的影响。

我们重复这个过程，如果我们到达上述三种情况都不适用的点（例如，如果我们达到 Kx 的形式），我们说β约化终止。一些 SKI 表达式可以被β约化为单个 I，一些则被变为为另一个小表达式，而另一些则永远持续增长。如果 SKI 表达式可以被β约化为由 n 个字符组成的字符串，则我们说它的输出大小为 n。

例如，我们将 beta 减少应用于

SKS（KIS）：SKS（KIS） => K（KIS）（S（KIS）） => KIS => I

SKIΩ演算

单独的 SKI 演算并不比图灵机强大（事实上，它们具有相同的计算能力）。但是我们可以通过添加一个额外的符号$\mathrm{\Omega }$来大大增加它的强度：

$\mathrm{\Omega }xyz\Rightarrow y$如果x可以被β约化为I。否则$\mathrm{\Omega }xyz\Rightarrow z$.

如果我们从一串长度为n的SKIΩ语句开始，并对其进行β约化，则最大可能的有限输出称为$\mathrm{\Xi }(n)$.需要注意的是，SKIΩ 演算语句可能是自相矛盾的（它可能会询问自己的停止，从而导致运算器在不停止的情况下停止的情况），我们在计算过程中需要忽略此类语句。

一些取值

一些确切的值和下界如下所示：

$\mathrm{\Xi }(1)=1$

$\mathrm{\Xi }(2)=2$

$\mathrm{\Xi }(3)=3$

$\mathrm{\Xi }(4)=4$

$\mathrm{\Xi }(5)=6$

$\mathrm{\Xi }(6)=17$

$\mathrm{\Xi }(7)=51$

$\mathrm{\Xi }(8)\ge 137$

$\mathrm{\Xi }(9)\ge 519$

$\mathrm{\Xi }(10)\ge 1041$

$\mathrm{\Xi }(11)\ge 2085$

$\mathrm{\Xi }(12)\ge 4173$

$\mathrm{\Xi }(n)>261\times 2^{n-8}-3\text{ (for }n\ge 9)$

Lawrence Hollom 通过在 SKI 演算中构建FGH，发现了更强的下界，后来由 Komi Amiko 改进了。这种构造为函数的较弱版本的下界，由于缺少对运算符Ω的运用：

$\mathrm{\Xi }(16)\ge 2^{2^9}+1>f_3(2)$

$\mathrm{\Xi }(21)>f_4(2)$

$\mathrm{\Xi }(25)>f_{\omega +1}(2)$

$\mathrm{\Xi }(38)>f_{{\omega }^2+1}(2)$

$\mathrm{\Xi }(56)>f_{{\omega }^{\omega }+1}(2)$

$\mathrm{\Xi }(117)>f_{{\omega }^{{\omega }^{\omega }}+1}(2)$

$\mathrm{\Xi }(2120)>f_{{\epsilon }_0}(5)$

$\mathrm{\Xi }(2123)>f_{{\epsilon }_0+1}(3)$

$\mathrm{\Xi }(2171)>f_{{\epsilon }_0\omega +1}(3)=f_{{\omega }^{{\epsilon }_0+1}+1}(3)$

以下是将具有最大输出的SKIΩ表达式的表格.注意大于7的式子未必是最优的。

$n$	最大输出长度的表达式
1	S
2	S(S)
3	S(SS)
4	S(SSS)
5	SSS(SI)
6	SSS(SI)S
7	SSS(SI)SΩ
8	SSK(S(SSΩ))S
9	SSI((S(SS)S)S)K
10	SSI((S(SS)S)S)KS
11	SSI((S(SS)S)S)KKS
12	SSI((S(SS)S)S)KKKS