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\):
    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 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 (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 Edit


An expansion of the tree (((()))), showing that Hydra(3) = 37

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

See also Edit