Ξ函数：修订间差异

2025年8月20日 (三) 16:20的最新版本

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

定义

SKI 演算

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

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

$𝐈 x \Rightarrow x$
$𝐊 x y \Rightarrow x$
$𝐒 x y z \Rightarrow x z (y z)$

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

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

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

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

SKIΩ 演算

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

$Ω x y z \Rightarrow y$ 如果 x 可以被 β 约化为 I。否则 $Ω x y z \Rightarrow z$ 。

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

取值

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

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

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

$Ξ (16) \geq 2^{2^{9}} + 1 > f_{3} (2)$

$Ξ (21) > f_{4} (2)$

$Ξ (25) > f_{ω + 1} (2)$

$Ξ (38) > f_{ω^{2} + 1} (2)$

$Ξ (56) > f_{ω^{ω} + 1} (2)$

$Ξ (117) > f_{ω^{ω^{ω}} + 1} (2)$

$Ξ (2120) > f_{ε_{0}} (5)$

$Ξ (2123) > f_{ε_{0} + 1} (3)$

$Ξ (2171) > f_{ε_{0} \cdot ω + 1} (3) = f_{ω^{ε_{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

参考资料

↑ 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
↑ Amiko, Komi (2020). Large numbers in the SKI combinator calculus. (EB/OL). https://komiamiko.me/math/ordinals/2020/06/21/ski-numerals.html

[1] 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

[2] Amiko, Komi (2020). Large numbers in the SKI combinator calculus. (EB/OL). https://komiamiko.me/math/ordinals/2020/06/21/ski-numerals.html

[1]

[2]

@@ 第1行： / 第1行： @@
-Ξ函数是Adam P. Goucher定义的一个快速增长的不可计算函数。它的“增长率”被估算为OFP。
+'''Ξ 函数'''是由 Adam P. Goucher 定义的一个快速增长的[[CKO#不可计算函数|不可计算函数]]。它的“[[增长率]]”被估算为 OFP。
-== 定义 ==
+=== 定义 ===
-=== SKI演算 ===
+==== SKI 演算 ====
-Ξ函数的定义基于SKI演算，SKI演算是组合逻辑的一个子系统，它是<math>\lambda</math>演算的前身。SKI演算是一颗二叉树，其中叶子是组合子为三个符号S、K、I，它们使用括号来表示树。SKI程序的一个简单的例子是<math>(((SK)S)((KI)S))</math>.我们默认它们是左结合的。因此可以将其简化为<math>SKS(KIS)</math>.
+Ξ 函数的定义基于 SKI 演算，SKI 演算是组合逻辑的一个子系统，它是 λ-演算的前身。SKI 演算是一颗二叉树，其中叶子是组合子为三个符号S、K、I，它们使用括号来表示树。SKI 程序的一个简单的例子是 <math>(((SK)S)((KI)S))</math>。我们默认它们是左结合的。因此可以将其简化为 <math>SKS(KIS)</math>。
-与 <math>\lambda</math>演算一样，SKI演算也有一个称为β约化的过程，这里用<math>\Rightarrow</math>表示。我们采用左组合的方式，并根据以下规则对树进行约化：
+与 λ-演算一样，SKI 演算也有一个称为 β 约化的过程，这里用 <math>\Rightarrow</math> 表示。我们采用左组合的方式，并根据以下规则对树进行约化：
 # <math>\mathbf{I}x \Rightarrow x</math>
@@ 第12行： / 第12行： @@
 # <math>\mathbf{S}xyz \Rightarrow xz(yz)</math>
-这些规则需要进行一些澄清。这里x,y,z表示任何有效的树，而不仅仅是单个符号。这些规则适用于树的最左侧部分，因此任何剩余的符号都不会受到这些转换的影响。
+这些规则需要进行一些澄清。这里 x,y,z 表示任何有效的树，而不仅仅是单个符号。这些规则适用于树的最左侧部分，因此任何剩余的符号都不会受到这些转换的影响。
-我们重复这个过程，如果我们到达上述三种情况都不适用的点（例如，如果我们达到 '''K'''''x'' 的形式），我们说β约化终止。一些 SKI 表达式可以被β约化为单个 '''I'''，一些则被变为为另一个小表达式，而另一些则永远持续增长。如果 SKI 表达式可以被β约化为由 ''n'' 个字符组成的字符串，则我们说它的输出大小为 ''n''。
+我们重复这个过程，如果我们到达上述三种情况都不适用的点（例如，如果我们达到 '''K'''''x'' 的形式），我们说 β 约化终止。一些 SKI 表达式可以被 β 约化为单个 '''I'''，一些则被变为为另一个小表达式，而另一些则永远持续增长。如果 SKI 表达式可以被 β 约化为由 ''n'' 个字符组成的字符串，则我们说它的输出大小为 ''n''。
 例如，我们将 beta 减少应用于
@@ 第20行： / 第20行： @@
 <code>SKS（KIS）：SKS（KIS） => K（KIS）（S（KIS）） => KIS => I</code>
-=== SKIΩ演算 ===
+==== SKIΩ 演算 ====
-单独的 SKI 演算并不比图灵机强大（事实上，它们具有相同的计算能力）。但是我们可以通过添加一个额外的符号<math>\Omega</math>来大大增加它的强度：
+单独的 SKI 演算并不比[[忙碌海狸函数#图灵机|图灵机]]强大（事实上，它们具有相同的计算能力）。但是我们可以通过添加一个额外的符号 <math>\Omega</math> 来大大增加它的强度：
-<math>\Omega xyz \Rightarrow y</math>如果x可以被β约化为I。否则<math>\Omega xyz \Rightarrow z </math>.
+<math>\Omega xyz \Rightarrow y</math> 如果 x 可以被 β 约化为 I。否则 <math>\Omega xyz \Rightarrow z </math>。
-如果我们从一串长度为n的SKIΩ语句开始，并对其进行β约化，则最大可能的有限输出称为<math>\Xi(n) </math>.需要注意的是，SKIΩ 演算语句可能是自相矛盾的（它可能会询问自己的停止，从而导致运算器在不停止的情况下停止的情况），我们在计算过程中需要忽略此类语句。
+如果我们从一串长度为 n 的 SKIΩ 语句开始，并对其进行β约化，则最大可能的有限输出称为 <math>\Xi(n) </math>。需要注意的是，SKIΩ 演算语句可能是自相矛盾的（它可能会询问自己的停止，从而导致运算器在不停止的情况下停止的情况），我们在计算过程中需要忽略此类语句。
-== 一些取值 ==
+=== 取值 ===
 一些确切的值和下界如下所示：
-<math>\Xi(1) = 1 </math>
+* <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>
-<math>\Xi(2) = 2 </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(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)
@@ 第81行： / 第69行： @@
   </math>
-<math>\Xi(2171) > f_{\varepsilon_0\omega+1}(3) = f_{\omega^{\varepsilon_0+1}+1}(3)  </math>
+<math>\Xi(2171) > f_{\varepsilon_0\cdot \omega+1}(3) = f_{\omega^{\varepsilon_0+1}+1}(3)  </math>
-以下是将具有最大输出的SKIΩ表达式的表格.注意大于7的式子未必是最优的。
+以下是将具有最大输出的 SKIΩ 表达式的表格，注意大于 7 的式子未必是最优的。
 {| class="wikitable"
 |+
@@ 第125行： / 第113行： @@
 |SSI((S(SS)S)S)KKKS
 |}
+== 参考资料 ==
+<references />{{默认排序:相关问题}}
+[[分类:记号]]