查看“︁Ξ函数”︁的源代码

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

=== 定义 ===

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

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

# <math>\mathbf{I}x \Rightarrow x</math>
# <math>\mathbf{K}xy \Rightarrow x</math>
# <math>\mathbf{S}xyz \Rightarrow xz(yz)</math>

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

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

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

<code>SKS（KIS）：SKS（KIS） => K（KIS）（S（KIS）） => KIS => I</code>

==== SKIΩ 演算 ====
单独的 SKI 演算并不比[[忙碌海狸函数#图灵机|图灵机]]强大（事实上，它们具有相同的计算能力）。但是我们可以通过添加一个额外的符号 <math>\Omega</math> 来大大增加它的强度：

<math>\Omega xyz \Rightarrow y</math> 如果 x 可以被 β 约化为 I。否则 <math>\Omega xyz \Rightarrow z </math>。

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

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

* <math>\Xi(1) = 1 </math>
* <math>\Xi(2) = 2 </math>
* <math>\Xi(3) = 3 </math>
* <math>\Xi(4) = 4 </math>
* <math>\Xi(5) = 6 </math>
* <math>\Xi(6) = 17 </math>
* <math>\Xi(7) = 51 </math>
* <math>\Xi(8) \geq 137 </math>
* <math>\Xi(9) \geq 519 </math>
* <math>\Xi(10) \geq 1041 </math>
* <math>\Xi(11) \geq 2085 </math>
* <math>\Xi(12) \geq 4173 </math>
* <math>\Xi(n) > 261\times 2^{n-8}-3 \text{ (for } n\geq 9) </math>

Lawrence Hollom 通过在 SKI 演算中构建 FGH，发现了更强的下界，后来由 Komi Amiko 改进<ref>Hollom, Lawrence (2014). Bounding The Xi Function. ''(EB/OL)''. https://web.archive.org/web/20230810130633/https://sites.google.com/a/hollom.com/extremely-big-numbers/home/xi</ref><ref>Amiko, Komi (2020). Large numbers in the SKI combinator calculus. ''(EB/OL)''.  https://komiamiko.me/math/ordinals/2020/06/21/ski-numerals.html</ref>。这种构造为函数的较弱版本的下界，由于缺少对运算符 Ω 的运用：

<math>\Xi(16) \geq 2^{2^9}+1 > f_3(2)
 </math>

<math>\Xi(21) > f_4(2)
 </math>

<math>\Xi(25) > f_{\omega+1}(2) </math>

<math>\Xi(38) > f_{\omega^2+1}(2)
 </math>

<math>\Xi(56) > f_{\omega^\omega+1}(2)
 </math>

<math>\Xi(117) > f_{\omega^{\omega^\omega}+1}(2)
 </math>

<math>\Xi(2120) > f_{\varepsilon_0}(5)
 </math>

<math>\Xi(2123) > f_{\varepsilon_0+1}(3)
 </math>

<math>\Xi(2171) > f_{\varepsilon_0\cdot \omega+1}(3) = f_{\omega^{\varepsilon_0+1}+1}(3)  </math>

以下是将具有最大输出的 SKIΩ 表达式的表格，注意大于 7 的式子未必是最优的。
{| class="wikitable"
|+
!<math>n </math>
!最大输出长度的表达式
|-
|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
|}

== 参考资料 ==
<references />{{默认排序:相关问题}}
[[分类:记号]]