Ξ函数 - 版本历史

2025年8月20日 (三) 08:20 Z

2025-08-20T08:20:39Z

←上一版本		2025年8月20日 (三) 16:20的版本
第115行：		第115行：

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

Tabelog：修正参考资料

2025-07-30T05:38:11Z

修正参考资料

←上一版本		2025年7月30日 (三) 13:38的版本
第44行：		第44行：
	* <math>\Xi(n) > 261\times 2^{n-8}-3 \text{ (for } n\geq 9) </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>。这种构造为函数的较弱版本的下界，由于缺少对运算符 Ω 的运用：		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>\Xi(16) \geq 2^{2^9}+1 > f_3(2)

2025年7月29日 (二) 08:12 Tabelog

2025-07-29T08:12:06Z

←上一版本		2025年7月29日 (二) 16:12的版本
第1行：		第1行：
	'''Ξ 函数'''是由 Adam P. Goucher 定义的一个快速增长的[[不可计算函数]]。它的“[[增长率]]”被估算为 OFP。		'''Ξ 函数'''是由 Adam P. Goucher 定义的一个快速增长的[[CKO#不可计算函数\|不可计算函数]]。它的“[[增长率]]”被估算为 OFP。

	=== 定义 ===		=== 定义 ===
第30行：		第30行：
	一些确切的值和下界如下所示：		一些确切的值和下界如下所示：

	<math>\Xi(1) = 1 </math>		* <math>\Xi(1) = 1 </math>
			* <math>\Xi(2) = 2 </math>
	<math>\Xi(2) = 2 </math>		* <math>\Xi(3) = 3 </math>
			* <math>\Xi(4) = 4 </math>
	<math>\Xi(3) = 3 </math>		* <math>\Xi(5) = 6 </math>
			* <math>\Xi(6) = 17 </math>
	<math>\Xi(4) = 4 </math>		* <math>\Xi(7) = 51 </math>
			* <math>\Xi(8) \geq 137 </math>
	<math>\Xi(5) = 6 </math>		* <math>\Xi(9) \geq 519 </math>
			* <math>\Xi(10) \geq 1041 </math>
	<math>\Xi(6) = 17 </math>		* <math>\Xi(11) \geq 2085 </math>
			* <math>\Xi(12) \geq 4173 </math>
	<math>\Xi(7) = 51 </math>		* <math>\Xi(n) > 261\times 2^{n-8}-3 \text{ (for } n\geq 9) </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>。这种构造为函数的较弱版本的下界，由于缺少对运算符 Ω 的运用：		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>。这种构造为函数的较弱版本的下界，由于缺少对运算符 Ω 的运用：

2025年7月25日 (五) 11:12 Tabelog

2025-07-25T11:12:41Z

←上一版本		2025年7月25日 (五) 19:12的版本
第1行：		第1行：
	'''~~Ξ函数~~'''~~，是由Adam~~ P. ~~Goucher定义的一个快速增长的~~[[不可计算函数]]。它的“[[增长率]]”被估算为~~[[OFP]]。~~		'''Ξ 函数'''是由 Adam P. Goucher 定义的一个快速增长的[[不可计算函数]]。它的“[[增长率]]”被估算为 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>		# <math>\mathbf{I}x \Rightarrow x</math>
第12行：		第12行：
	# <math>\mathbf{S}xyz \Rightarrow xz(yz)</math>		# <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 减少应用于		例如，我们将 beta 减少应用于
第20行：		第20行：
	<code>SKS（KIS）：SKS（KIS） => K（KIS）（S（KIS）） => KIS => I</code>		<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Ω 演算语句可能是自相矛盾的（它可能会询问自己的停止，从而导致运算器在不停止的情况下停止的情况），我们在计算过程中需要忽略此类语句。

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

第56行：		第56行：
	<math>\Xi(n) > 261\times 2^{n-8}-3 \text{ (for } n\geq 9) </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>~~。这种构造为函数的较弱版本的下界，由于缺少对运算符Ω的运用：~~		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>\Xi(16) \geq 2^{2^9}+1 > f_3(2)
第83行：		第83行：
	<math>\Xi(2171) > f_{\varepsilon_0\cdot \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"		{\| class="wikitable"
	\|+		\|+

QWQ-bili：美化公式，添加引用

2025-07-15T10:22:00Z

美化公式，添加引用

←上一版本		2025年7月15日 (二) 18:22的版本
第1行：		第1行：
	~~Ξ函数是Adam~~ P. ~~Goucher定义的一个快速增长的不可计算函数。它的“增长率”被估算为OFP。~~		'''Ξ函数'''，是由Adam P. Goucher定义的一个快速增长的[[不可计算函数]]。它的“[[增长率]]”被估算为[[OFP]]。

	== 定义 ==		== 定义 ==
第21行：		第21行：

	=== 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>.
第81行：		第81行：
	</math>		</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的式子未必是最优的。

2025年7月15日 (二) 07:18 Z

2025-07-15T07:18:35Z

←上一版本		2025年7月15日 (二) 15:18的版本
第125行：		第125行：
	\|SSI((S(SS)S)S)KKKS		\|SSI((S(SS)S)S)KKKS
	\|}		\|}

			== 参考资料 ==
			<references />
			[[分类:记号]]

Z：创建页面，内容为“Ξ函数是Adam P. Goucher定义的一个快速增长的不可计算函数。它的“增长率”被估算为OFP。 == 定义 == === SKI演算 === Ξ函数的定义基于SKI演算，SKI演算是组合逻辑的一个子系统，它是 $\lambda$ 演算的前身。SKI演算是一颗二叉树，其中叶子是组合子为三个符号S、K、I，它们使用括号来表示树。SKI程序的一个简单的例子是 $(((SK)S)((KI)S))$ .我们默…”

2025-07-15T07:18:08Z

创建页面，内容为“Ξ函数是Adam P. Goucher定义的一个快速增长的不可计算函数。它的“增长率”被估算为OFP。 == 定义 == === SKI演算 === Ξ函数的定义基于SKI演算，SKI演算是组合逻辑的一个子系统，它是<math>\lambda</math>演算的前身。SKI演算是一颗二叉树，其中叶子是组合子为三个符号S、K、I，它们使用括号来表示树。SKI程序的一个简单的例子是<math>(((SK)S)((KI)S))</math>.我们默…”

新页面

Ξ函数是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
|}