*See also: Buchholz hydra*

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 Edit

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\):
- \(a\) is deleted from T.
- 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\).- Delete it.
- 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 Edit

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 (H_{1}H_{2}...H_{n}) = \(\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\).

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 Edit

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.

## External links Edit

Bauer, Andrej. The hydra game.

- Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic",
*Bulletin of the London Mathematical Society***14**: 285–293. - Weisstein, Eric W., "Goodstein Sequence",
*MathWorld*. - Some elements of a proof that Goodstein's theorem is not a theorem of PA, from an undergraduate thesis by Justin T Miller
- A Classification of non stanard models of Peano Arithmetic by Goodstein's theorem - Thesis by Dan Kaplan, Franklan and Marshall College Library
- Definitions of Goodstein sequences in the programming languages Ruby and Haskell, as well as a large-scale plot
- Goodstein Sequences: The Power of a Detour via Infinity - good exposition with illustrations of Goodstein Sequences and the hydra game.

## See also Edit

**By Harvey Friedman:** Mythical tree problem · Friedman's vector reduction problem · Friedman's finite ordered tree problem · block subsequence theorem n(4) · Friedman's circle theorem · TREE sequence TREE(3) · subcubic graph number SCG(13) · transcendental integer · finite promise games · Friedman's finite trees · Greedy clique sequence**Hydras:** **Kirby-Paris** · Beklemishev's worms · Buchholz**Miscellaneous:** Factorial · Folkman's number · Exploding Tree Function · Graham's number · fusible number · Goodstein function · Laver table