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

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

== 定义 ==

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

与 <math>\lambda</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. [https://web.archive.org/web/20230810130633/https://sites.google.com/a/hollom.com/extremely-big-numbers/home/xi Bounding The Xi Function]. Retrieved 2014-08-21.</ref><ref>Amiko, Komi. [https://komiamiko.me/math/ordinals/2020/06/21/ski-numerals.html Large numbers in the SKI combinator calculus]. Retrieved 2020-07-20.</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\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 />
[[分类:记号]]