查看“︁Kirby-Paris Hydra”︁的源代码

'''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|400px|无框|居中]]

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

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

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

* 游戏从一棵有 <math>n+1</math> 个节点的链状有序有根树 <math>T</math> 开始；
* 第 <math>n</math> 回合，选择 <math>T</math> 的最右边的叶子节点 <math>a</math>，设 <math>a</math> 的父节点为 <math>b</math>，依次执行以下操作（称为一次砍树）：
*# 删除 <math>a</math>；
*# 若 <math>b</math> 不是根节点，取以 <math>b</math> 为根的子树 <math>T'</math>，将其复制 <math>n</math> 次，连接到 <math>b</math> 的父节点上。
*如果某步操作后只剩下根节点，游戏结束。

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

例如：设 <math>n=3</math>，考虑这样的一棵树 <math>(((()))(()(){\color{red}()}))</math>。

将红色的括号删除后，树的变化如下：<math>(((())){\color{blue}(()(){\color{red}()})})\rightarrow
(((())){\color{blue}(()())})\rightarrow
(((())){\color{blue}(()())}{\color{green}(()())}{\color{green}(()())}{\color{green}(()())})</math>

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

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

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

第 2 次砍树：

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

依此类推：

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

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

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

其证明概要如下：

我们给每个非空树对应一个序数：

* 只含根节点的树 <math>()</math> 对应 0
* 若树 <math>T_1,T_2,\cdots,T_n</math> 分别对应序数 <math>H_1,H_2,\cdots,H_n</math>（通过重新排列，不妨设 <math>H_1\ge H_2\ge\cdots\ge H_n</math>），则<math>(T_1T_2\cdots T_n)</math>对应<math>\omega^{H_1}+\omega^{H_2}+\cdots+\omega^{H_n}</math>
例如，<math>(((()))(()()()))
=\omega^{\omega^{\omega^0}}+\omega^{\omega^0+\omega^0+\omega^0}
=\omega^\omega+\omega^3</math>。

对树的深度归纳可知，每棵树对应的序数都小于 <math>\varepsilon_0</math>。

设初始的树为 <math>T</math>。我们证明：砍树操作后，树对应的序数严格减小。

* 若选取节点的父节点为根节点，则 <math>T=(T_1())</math>，其对应的序数形如 <math>H+1</math>，砍树操作后变为 <math>H</math>，严格减小；
* 否则，设其父节点所在的子树为 <math>(T_1(T_3{\color{red}()})T_2)</math>，其对应序数 <math>H_1+\omega^{H_3+1}+H_2</math>。进行砍树操作后，该子树变为 <math>(T_1(T_3)(T_3)\cdots(T_3)T_2)</math>，对应序数 <math>H_1+\omega^{H_3}(n+1)+H_2</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 函数 ===
我们用 <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</math> 较小时 <math>\rm{Hydra(n)}</math> 的值：

* <math>\rm{Hydra(0)}=0</math>
* <math>\rm{Hydra(1)}=1</math>
* <math>\rm{Hydra(2)}=3</math>
* <math>\rm{Hydra(3)}=37</math>
* <math>{\rm Hydra(4)}>f_{\omega 2+4}(5)</math>
* <math>{\rm Hydra(5)}>f_{\omega^{\omega 2+4}}(5)</math>

其中<math>f</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 />{{默认排序:相关问题}}
[[分类:记号]]