FANDOM


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

Hydra3

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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.