Ξ函数

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

定义

SKI 演算

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

与 λ-演算一样，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\cdot \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