10,563 Pages

The Kirby-Paris hydra game is a one-player game played on a tree that can last a very large number of turns. It gives rise to a function $$\text{Hydra}(n)$$ that eventually dominates all recursive functions which are provably total in Peano arithmetic, and is itself provably total in PA + "$$\varepsilon_0$$ is well-ordered."

The game is closely related to Beklemishev's worms.

## Rules

The game is played as follows:

• We start with a finite rooted tree $$T$$. Call its root $$r$$.
• Jonathan picks a leaf vertex of the tree and a natural number $$n$$. Call the leaf $$a$$ and its parent $$b$$:
1. $$a$$ is deleted from T.
2. If $$b = r$$, nothing happens. Otherwise, let $$c$$ be the parent of $$b$$. Consider the subtree consisting of $$b$$ and all its children; copy this subtree $$n$$ times. Attach all these copies to $$c$$.

This can be expressed equivalently using strings of parentheses:

• Start with a finite sequence of matched parentheses such as (()(()(())((())))).
• Pick an empty pair () and a natural number $$n$$.
1. Delete it.
2. If its parent is not the outermost pair, take its parent and append $$n$$ copies of it.

For example, at step 3 we can transform (()(()())) into (()(())(())(())(())).

Jonathan keeps picking leaves and $$n$$'s and chopping off hydra heads. He wins when the hydra is reduced to a root node.

## Hydra theorem

We define a strategy on $$T$$ as a sequence of leaves and values of $$n$$ that continues as long as the game does. A winning strategy is one that eventually defeats the hydra, and a losing strategy is one that does not.

Some strategies are obviously winning strategies. Repeatedly setting $$n = 0$$ ensures that the hydra never grows back, for instance. But many strategies (especially for large $$n$$) can cause hydras to grow very rapidly, raising the question: can Jonathan ever lose by allowing the hydra to grow indefinitely? Kirby and Paris showed the answer is no — Jonathan always wins, and there are no losing strategies for any hydra. This fact is called the hydra theorem, and it is unprovable in Peano arithmetic. We will recreate a sketch of their proof of the theorem:

Proof: We assign an ordinal to each possible tree, defining () = 0 and (H1H2...Hn) = $$\omega^{H_1} + \omega^{H_2} + \ldots + \omega^{H_n}$$ where $$H_1 \geq H_2 \geq \ldots \geq H_n$$. (This ignores the orders of nodes, but order does not affect the hydra theorem.) It can be shown that removing a leaf strictly decreases the hydra $$H$$ regardless of the value of $$n$$:

• If the leaf node we select is a child of the root node, the result is $$H - 1$$, which is strictly smaller than $$H$$.
• If the leaf node we select is a child of node $$J = \omega^{K+1}$$, then chopping it results in $$\omega^Kn$$, which is strictly smaller than $$J$$ for finite $$n$$.

Since the hydra's value always decreases, its ordinal will reach 0 in a finite amount of time.

This strategy is useful for proving the termination of Friedmanesque computable one-player games such as the Buchholz hydra. It can also be applied to Goodstein sequences, although less elegantly.

## Hydra function

Often, the number of steps required to defeat the hydra is very large. Since there are so many parameters at work here, we will simplify things using a few conventions:

• Each hydra is a path of length $$k$$, that is, a chain of $$k + 1$$ nodes.
• The strategy always picks the rightmost node using $$n = 1$$, then $$n = 2$$, then $$n = 3$$, etc. until the game ends.

Using these hydras and strategies, define $$\text{Hydra}(k)$$ as the number of turns needed to win the game. Then

\begin{eqnarray*} \text{Hydra}(0) &=& 0\\ \text{Hydra}(1) &=& 1\\ \text{Hydra}(2) &=& 3\\ \text{Hydra}(3) &=& 37\\ \text{Hydra}(4) &>& f_{\omega*2 +4}(5) \approx \{5,5,4,3\} >> \text{Graham's number}\\  \text{Hydra}(5) &>& f_{\omega^{\omega*2 + 4}}(5) \approx \{5,5 (1) (1) 5,5,5,5,5\}\\  \end{eqnarray*}

The computation of $$\text{Hydra}(3)$$ is shown to the right.

In general, $$f_{\omega^{\omega^{\cdots^{\omega2+4}}}}(6) > \text{Hydra}(n) > f_{\omega^{\omega^{\cdots^{\omega2+4}}}}(5) > X \uparrow\uparrow (n-4) \&\ 5$$, where are $$n-3$$ copies of $$\omega$$ in each tower. $$\text{Hydra}(n)$$ eventually dominates all functions provably recursive in Peano arithmetic, and it can be approximated with the function $$f_{\varepsilon_0}$$. In particular, $$\text{Hydra} >^* f_\alpha$$ for all $$\alpha < \varepsilon_0$$, but $$\text{Hydra} <^* f_{\varepsilon_0 + 1}$$. This puts the hydra function on par with Goodstein sequences and tetrational BEAF arrays.

Community content is available under CC-BY-SA unless otherwise noted.