Kirby-Paris Hydra

Kirby-Paris Hydra（KP Hydra）是在一棵树上进行的单人游戏，需要很长时间才能终止。由此游戏导出的函数 $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{n}\mathrm{)}$ 的增长率超过了皮亚诺公理体系可证明停机的一切递归函数。它与 Beklemishev's worm 密切相关。

有序有根树

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

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

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

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

规则

KP Hydra 游戏的规则如下：

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

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

例如：设 $n=3$，考虑这样的一棵树 $(((()))(()()()))$。

将红色的括号删除后，树的变化如下：$(((()))(()()()))\to (((()))(()()))\to (((()))(()())(()())(()())(()()))$

以 $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}(3)$ 为例，我们从一棵包含 4 个节点的链状有序有根树出发，进行第 1 次砍树：

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

第 2 次砍树：

依此类推：

经过 37 次砍树，这棵树只剩一个节点，游戏结束．所以 $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}(3)=37$．

停机性证明

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

其证明概要如下：

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

• 只含根节点的树 $()$ 对应 0
• 若树 $T_1,T_2,\cdots ,T_n$ 分别对应序数 $H_1,H_2,\cdots ,H_n$（通过重新排列，不妨设 $H_1\ge H_2\ge \cdots \ge H_n$），则$(T_1{T}_2\cdots T_n)$对应${\omega }^{H_1}+{\omega }^{H_2}+\cdots +{\omega }^{H_n}$

例如，$(((()))(()()()))={\omega }^{{\omega }^{{\omega }^0}}+{\omega }^{{\omega }^0+{\omega }^0+{\omega }^0}={\omega }^{\omega }+{\omega }^3$。

对树的深度归纳可知，每棵树对应的序数都小于 ${\epsilon }_0$。

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

• 若选取节点的父节点为根节点，则 $T=(T_1())$，其对应的序数形如 $H+1$，砍树操作后变为 $H$，严格减小；
• 否则，设其父节点所在的子树为 $(T_1(T_3())T_2)$，其对应序数 $H_1+{\omega }^{H_3+1}+H_2$。进行砍树操作后，该子树变为 $(T_1(T_3)(T_3)\cdots (T_3)T_2)$，对应序数 $H_1+{\omega }^{H_3}(n+1)+H_2$，严格减小。

假设游戏从 $T$ 开始可以无限地进行下去，我们可以得到一系列树 $T_1,T_2,\cdots$，它们对应的序数满足 ${\epsilon }_0>H_1>H_2>\cdots$，这与 ${\epsilon }_0$ 的良序性矛盾。故游戏总会在有限步内终止。

Hydra 函数

我们用 $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{n}\mathrm{)}$ 表示以下特殊的 KP Hydra 游戏终止所需要的步数：

• 初始树为含 $n+1$ 个节点的链，即形如 $((\cdots ()\cdots ))$ 的树；
• 每次操作总选取最右边的节点。

下面列出 $n$ 较小时 $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{n}\mathrm{)}$ 的值：

• $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{0}\mathrm{)}\mathrm{=}\mathrm{0}$
• $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{1}\mathrm{)}\mathrm{=}\mathrm{1}$
• $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{2}\mathrm{)}\mathrm{=}\mathrm{3}$
• $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{3}\mathrm{)}\mathrm{=}\mathrm{3}\mathrm{7}$
• $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{4}\mathrm{)}>f_{\omega 2+4}(5)$
• $\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{5}\mathrm{)}>f_{{\omega }^{\omega 2+4}}(5)$

其中$f$为快速增长层级。一般地，记 ${\alpha }_n={\omega }^{{\omega }^{{\cdots }^{\omega 2+4}}}$，其中有 $n-3$ 个 $\omega$，则 $f_{\alpha }(5)<\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{n}\mathrm{)}<f_{\alpha }(6)$。因此，$\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{n}\mathrm{)}$ 的增长率为 ${\epsilon }_0$。