Kirby-Paris Hydra - 版本历史

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

2025-08-20T08:14:03Z

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

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

Tabelog：修正参考资料

2025-07-30T05:31:55Z

修正参考资料

←上一版本		2025年7月30日 (三) 13:31的版本
第1行：		第1行：
	'''Kirby-Paris Hydra（KP Hydra）'''是在一棵树上进行的单人游戏，需要很长时间才能终止。<ref>Kirby, L.; Paris, J. (1982)~~, "~~Accessible independence results for Peano arithmetic", ''Bulletin of the London Mathematical Society'' ~~'''~~14~~'''~~: 285–293.</ref>由此游戏导出的函数 <math>\rm{Hydra(n)}</math> 的增长率超过了[[皮亚诺公理体系]]可证明停机的一切递归函数。它与 [[Beklemishev's Worm\|Beklemishev's worm]] 密切相关。		'''Kirby-Paris Hydra（KP Hydra）'''是在一棵树上进行的单人游戏，需要很长时间才能终止。<ref>Kirby, L., & Paris, J. (1982). Accessible independence results for Peano arithmetic. ''Bulletin of the London Mathematical Society'', 14: 285–293.</ref>由此游戏导出的函数 <math>\rm{Hydra(n)}</math> 的增长率超过了[[皮亚诺公理体系]]可证明停机的一切递归函数。它与 [[Beklemishev's Worm\|Beklemishev's worm]] 密切相关。

	=== 有序有根树 ===		=== 有序有根树 ===
第68行：		第68行：

	=== Hydra 函数 ===		=== Hydra 函数 ===
	我们用 <math>\rm{Hydra(n)}</math> 表示以下特殊的 KP Hydra 游戏终止所需要的步数：<ref>[https://googology.fandom.com/wiki/Kirby-Paris_hydra ~~Kirby-Paris hydra \| Googology Wiki \| Fandom]~~</ref>		我们用 <math>\rm{Hydra(n)}</math> 表示以下特殊的 KP Hydra 游戏终止所需要的步数：<ref>Googology Wiki. Kirby-Paris Hydra. ''(EB/OL), Googology Wiki''. https://googology.fandom.com/wiki/Kirby-Paris_hydra</ref>

	* 初始树为含 <math>n+1</math> 个节点的链，即形如 <math>((\cdots()\cdots))</math> 的树；		* 初始树为含 <math>n+1</math> 个节点的链，即形如 <math>((\cdots()\cdots))</math> 的树；

2025年7月29日 (二) 11:24 Tabelog

2025-07-29T11:24:05Z

显示更改

QWQ-bili：调整参考文献及排版

2025-07-08T18:42:04Z

调整参考文献及排版

←上一版本		2025年7月9日 (三) 02:42的版本
第67行：		第67行：
	假设游戏从<math>T</math>开始可以无限地进行下去，我们可以得到一系列树<math>T_1,T_2,\cdots</math>，它们对应的序数满足<math>\varepsilon_0>H_1>H_2>\cdots</math>，这与<math>\varepsilon_0</math>的良序性矛盾。故游戏总会在有限步内终止。		假设游戏从<math>T</math>开始可以无限地进行下去，我们可以得到一系列树<math>T_1,T_2,\cdots</math>，它们对应的序数满足<math>\varepsilon_0>H_1>H_2>\cdots</math>，这与<math>\varepsilon_0</math>的良序性矛盾。故游戏总会在有限步内终止。

	== Hydra 函数<ref>[https://googology.fandom.com/wiki/Kirby-Paris_hydra Kirby-Paris hydra \| Googology Wiki \| Fandom]</ref> ==		== Hydra 函数 ==
	~~我们用<math>\rm{Hydra(n)}</math>表示以下特殊的 KP Hydra 游戏终止所需要的步数：~~		我们用<math>\rm{Hydra(n)}</math>表示以下特殊的 KP Hydra 游戏终止所需要的步数<ref>[https://googology.fandom.com/wiki/Kirby-Paris_hydra Kirby-Paris hydra \| Googology Wiki \| Fandom]</ref>：

	* 初始树为含<math>n+1</math>个节点的链，即形如<math>((\cdots()\cdots))</math>的树；		* 初始树为含<math>n+1</math>个节点的链，即形如<math>((\cdots()\cdots))</math>的树；
第88行：		第88行：

	一般地，记<math>\alpha_n=\omega^{\omega^{\cdots^{\omega 2+4}}}</math>，其中有<math>n-3</math>个<math>\omega</math>，则<math>f_\alpha(5)<{\rm Hydra(n)}<f_\alpha(6)</math>。因此，<math>{\rm Hydra(n)}</math>的增长率为<math>\varepsilon_0</math>。		一般地，记<math>\alpha_n=\omega^{\omega^{\cdots^{\omega 2+4}}}</math>，其中有<math>n-3</math>个<math>\omega</math>，则<math>f_\alpha(5)<{\rm Hydra(n)}<f_\alpha(6)</math>。因此，<math>{\rm Hydra(n)}</math>的增长率为<math>\varepsilon_0</math>。

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

2025年7月8日 (二) 07:05 Z

2025-07-08T07:05:15Z

←上一版本		2025年7月8日 (二) 15:05的版本
第20行：		第20行：
	*# 删除 <math>a</math>；		*# 删除 <math>a</math>；
	*# 若 <math>b</math> 不是根节点，取以 <math>b</math> 为根的子树 <math>T'</math>，将其复制 <math>n</math> 次，连接到 <math>b</math> 的父节点上．		*# 若 <math>b</math> 不是根节点，取以 <math>b</math> 为根的子树 <math>T'</math>，将其复制 <math>n</math> 次，连接到 <math>b</math> 的父节点上．
	* 如果某步操作后只剩下根节点，游戏结束．		*如果某步操作后只剩下根节点，游戏结束．

	我们可以用括号表示树：每一对括号表示一个节点，最外层的括号表示根节点，每个括号内层的括号表示它的子节点。		我们可以用括号表示树：每一对括号表示一个节点，最外层的括号表示根节点，每个括号内层的括号表示它的子节点。
第88行：		第88行：

	一般地，记<math>\alpha_n=\omega^{\omega^{\cdots^{\omega 2+4}}}</math>，其中有<math>n-3</math>个<math>\omega</math>，则<math>f_\alpha(5)<{\rm Hydra(n)}<f_\alpha(6)</math>。因此，<math>{\rm Hydra(n)}</math>的增长率为<math>\varepsilon_0</math>。		一般地，记<math>\alpha_n=\omega^{\omega^{\cdots^{\omega 2+4}}}</math>，其中有<math>n-3</math>个<math>\omega</math>，则<math>f_\alpha(5)<{\rm Hydra(n)}<f_\alpha(6)</math>。因此，<math>{\rm Hydra(n)}</math>的增长率为<math>\varepsilon_0</math>。
			<references />
			[[分类:记号]]

2025年7月7日 (一) 06:18 Zhy137036

2025-07-07T06:18:49Z

←上一版本		2025年7月7日 (一) 14:18的版本
第7行：		第7行：
	正如“有序有根树”的名字所说，“有序有根树”有一个节点是树根（根节点），根节点下面挂着若干（有限）棵子树，每棵子树也是一个“有序有根树”．这些子树从左到右依次排列，不能交换顺序，这就是“有序”的含义．下图是两棵不同的有序有根树．		正如“有序有根树”的名字所说，“有序有根树”有一个节点是树根（根节点），根节点下面挂着若干（有限）棵子树，每棵子树也是一个“有序有根树”．这些子树从左到右依次排列，不能交换顺序，这就是“有序”的含义．下图是两棵不同的有序有根树．

	[[文件:KP Hydra 1.png\|无框\|居中]]		[[文件:KP Hydra 1.png\|400px\|无框\|居中]]

	如果一个节点下面没有挂任何子树，那么称它是叶子节点．如果节点 <math>a</math> 在节点 <math>b</math> 下面且二者相邻，则称 <math>a</math> 是 <math>b</math> 的子节点，<math>b</math> 是 <math>a</math> 的父节点．根节点不是任何节点的子节点．		如果一个节点下面没有挂任何子树，那么称它是叶子节点．如果节点 <math>a</math> 在节点 <math>b</math> 下面且二者相邻，则称 <math>a</math> 是 <math>b</math> 的子节点，<math>b</math> 是 <math>a</math> 的父节点．根节点不是任何节点的子节点．
第33行：		第33行：

	[[文件:KP Hydra 2.png\|300px\|居中\|无框]]		[[文件:KP Hydra 2.png\|300px\|居中\|无框]]

			其中即将被删除的节点标为红色，新复制出来的节点标为蓝色．

	第 <math>2</math> 次砍树：		第 <math>2</math> 次砍树：

Zhy137036：/* 规则 */

2025-07-07T06:16:44Z

规则

←上一版本		2025年7月7日 (一) 14:16的版本
第32行：		第32行：
	以 <math>\mathrm{Hydra}(3)</math> 为例，我们从一棵包含 <math>4</math> 个节点的链状有序有根树出发，进行第 <math>1</math> 次砍树：		以 <math>\mathrm{Hydra}(3)</math> 为例，我们从一棵包含 <math>4</math> 个节点的链状有序有根树出发，进行第 <math>1</math> 次砍树：

	[[文件:KP Hydra 2.png\|居中\|无框]]		[[文件:KP Hydra 2.png\|300px\|居中\|无框]]

	第 <math>2</math> 次砍树：		第 <math>2</math> 次砍树：

	[[文件:KP Hydra 3.png\|居中\|无框]]		[[文件:KP Hydra 3.png\|500px\|居中\|无框]]

	~~依此类推，经过~~ <math>37</math> 次砍树，这棵树只剩一个节点，游戏结束．所以 <math>\mathrm{Hydra}(3)=37</math>．		依此类推：

			[[文件:KP Hydra 4.png\|700px\|居中\|无框]]

			经过 <math>37</math> 次砍树，这棵树只剩一个节点，游戏结束．所以 <math>\mathrm{Hydra}(3)=37</math>．

	== 停机性证明 ==		== 停机性证明 ==

Zhy137036：/* 有序有根树 */

2025-07-07T05:49:36Z

有序有根树

←上一版本		2025年7月7日 (一) 13:49的版本
第10行：		第10行：

	如果一个节点下面没有挂任何子树，那么称它是叶子节点．如果节点 <math>a</math> 在节点 <math>b</math> 下面且二者相邻，则称 <math>a</math> 是 <math>b</math> 的子节点，<math>b</math> 是 <math>a</math> 的父节点．根节点不是任何节点的子节点．		如果一个节点下面没有挂任何子树，那么称它是叶子节点．如果节点 <math>a</math> 在节点 <math>b</math> 下面且二者相邻，则称 <math>a</math> 是 <math>b</math> 的子节点，<math>b</math> 是 <math>a</math> 的父节点．根节点不是任何节点的子节点．

			如果一棵树里，除了叶子节点外，每个节点下只有一棵子树，则称这棵树是链状树．

	== 规则 ==		== 规则 ==

Zhy137036：/* 规则 */

2025-07-07T05:01:04Z

规则

←上一版本		2025年7月7日 (一) 13:01的版本
第14行：		第14行：
	KP Hydra 游戏的规则如下：		KP Hydra 游戏的规则如下：

	* ~~游戏从一棵有序有根树~~ <math>T</math> 开始；		* 游戏从一棵有 <math>n+1</math> 个节点的链状有序有根树 <math>T</math> 开始；
	* 第 <math>n</math> 回合，选择 <math>T</math> 的最右边的叶子节点 <math>a</math>，设 <math>a</math> 的父节点为 <math>b</math>，依次执行以下操作(称为一次砍树)：		* 第 <math>n</math> 回合，选择 <math>T</math> 的最右边的叶子节点 <math>a</math>，设 <math>a</math> 的父节点为 <math>b</math>，依次执行以下操作(称为一次砍树)：
	*# 删除 <math>a</math>；		*# 删除 <math>a</math>；
第27行：		第27行：
	(((())){\color{blue}(()())})\rightarrow		(((())){\color{blue}(()())})\rightarrow
	(((())){\color{blue}(()())}{\color{green}(()())}{\color{green}(()())}{\color{green}(()())})</math>		(((())){\color{blue}(()())}{\color{green}(()())}{\color{green}(()())}{\color{green}(()())})</math>

			以 <math>\mathrm{Hydra}(3)</math> 为例，我们从一棵包含 <math>4</math> 个节点的链状有序有根树出发，进行第 <math>1</math> 次砍树：

			[[文件:KP Hydra 2.png\|居中\|无框]]

			第 <math>2</math> 次砍树：

			[[文件:KP Hydra 3.png\|居中\|无框]]

			依此类推，经过 <math>37</math> 次砍树，这棵树只剩一个节点，游戏结束．所以 <math>\mathrm{Hydra}(3)=37</math>．

	== 停机性证明 ==		== 停机性证明 ==

2025年7月7日 (一) 04:40 Zhy137036

2025-07-07T04:40:33Z

←上一版本		2025年7月7日 (一) 12:40的版本
第1行：		第1行：
	'''Kirby-Paris Hydra(KP-Hydra)''' 是在一棵树上进行的单人游戏，需要很长时间才能终止<ref>Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic", ''Bulletin of the London Mathematical Society'' '''14''': 285–293.</ref>。由此游戏导出的函数<math>\rm{Hydra(n)}</math>的增长率超过了[[皮亚诺公理体系]]可证明停机的一切递归函数。它与[[Beklemishev's Worm\|Beklemishev's worm]]密切相关。		'''Kirby-Paris Hydra(KP Hydra)''' 是在一棵树上进行的单人游戏，需要很长时间才能终止<ref>Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic", ''Bulletin of the London Mathematical Society'' '''14''': 285–293.</ref>。由此游戏导出的函数<math>\rm{Hydra(n)}</math>的增长率超过了[[皮亚诺公理体系]]可证明停机的一切递归函数。它与[[Beklemishev's Worm\|Beklemishev's worm]]密切相关。

			== 有序有根树 ==

			KP Hydra 的规则定义在有序有根树上，所以有必要简单了解有序有根树的概念．

			正如“有序有根树”的名字所说，“有序有根树”有一个节点是树根（根节点），根节点下面挂着若干（有限）棵子树，每棵子树也是一个“有序有根树”．这些子树从左到右依次排列，不能交换顺序，这就是“有序”的含义．下图是两棵不同的有序有根树．

			[[文件:KP Hydra 1.png\|无框\|居中]]

			如果一个节点下面没有挂任何子树，那么称它是叶子节点．如果节点 <math>a</math> 在节点 <math>b</math> 下面且二者相邻，则称 <math>a</math> 是 <math>b</math> 的子节点，<math>b</math> 是 <math>a</math> 的父节点．根节点不是任何节点的子节点．

	== 规则 ==		== 规则 ==
	KP-Hydra 游戏的规则如下：		KP Hydra 游戏的规则如下：

	* 游戏从一棵有序有根树 <math>T</math> 开始；		* 游戏从一棵有序有根树 <math>T</math> 开始；
第19行：		第29行：

	== 停机性证明 ==		== 停机性证明 ==
	Kirby 和 Paris 证明了以下定理：无论初始的树T怎样选取，KP-Hydra 游戏总会在有限步内终止。		Kirby 和 Paris 证明了以下定理：无论初始的树T怎样选取，KP Hydra 游戏总会在有限步内终止。

	其证明概要如下：		其证明概要如下：
第40行：		第50行：

	== Hydra 函数<ref>[https://googology.fandom.com/wiki/Kirby-Paris_hydra Kirby-Paris hydra \| Googology Wiki \| Fandom]</ref> ==		== Hydra 函数<ref>[https://googology.fandom.com/wiki/Kirby-Paris_hydra Kirby-Paris hydra \| Googology Wiki \| Fandom]</ref> ==
	我们用<math>\rm{Hydra(n)}</math>表示以下特殊的 KP-Hydra 游戏终止所需要的步数：		我们用<math>\rm{Hydra(n)}</math>表示以下特殊的 KP Hydra 游戏终止所需要的步数：

	* 初始树为含<math>n+1</math>个节点的链，即形如<math>((\cdots()\cdots))</math>的树；		* 初始树为含<math>n+1</math>个节点的链，即形如<math>((\cdots()\cdots))</math>的树；

Kirby-Paris Hydra - 版本历史

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

Tabelog：​修正参考资料

2025年7月29日 (二) 11:24 Tabelog

QWQ-bili：​调整参考文献及排版

2025年7月8日 (二) 07:05 Z

2025年7月7日 (一) 06:18 Zhy137036

Zhy137036：​/* 规则 */

Zhy137036：​/* 有序有根树 */

Zhy137036：​/* 规则 */

2025年7月7日 (一) 04:40 Zhy137036

Tabelog：修正参考资料

QWQ-bili：调整参考文献及排版

Zhy137036：/* 规则 */

Zhy137036：/* 有序有根树 */

Zhy137036：/* 规则 */