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 游戏的规则如下：

• 游戏从一棵有根树T开始；
• 第n回合，选择T的一个叶子节点a，设a的父节点为b，依次执行以下操作(称为一次砍树)：
  1. 删除a；
  2. 若b不是根节点，取以b为根的子树T'，将其复制n次，连接到b的父节点上。
• 如果某步操作后只剩下根节点，游戏结束。

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

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

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

停机性证明

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)$，其中$f$为快速增长层级；

$\mathrm{H}\mathrm{y}\mathrm{d}\mathrm{r}\mathrm{a}\mathrm{(}\mathrm{5}\mathrm{)}>f_{{\omega }^{\omega 2+4}}(5)$

一般地，记${\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$。