Googology Wiki
Advertisement
Googology Wiki

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.[1] 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", and the game is also related to Gentzen's proof-reduction trees[2].

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\).
  • The player 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 (()(())(())(())(())).

The player 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 the player ever lose by allowing the hydra to grow indefinitely?

The answer is no. The player always wins and there are no losing strategies for any hydra. This is called hydra theorem. Kirby and Paris, who introduced the hydra game first, showed the hydra theorem in the case that \(n\) is equal to the number of rounds of the game. It is especially called Kirby-Paris hydra theorem.

The generalized version of the theorem is a corollary of Kirby-Paris hydra theorem. It was believed in this community that Kirby and Paris showed the generalized version, but the source of this article does not include such a result. Although the generalized version is a corrollary of the original version under some weak set theory, the statement that they showed the generalised version is wrong because they even does not state the generalized version. As we wrote, they only refered to the fact that the sequence for the case where \(n\) is the current turn count is a winning strategy. A similar made-up description is found in Buchholz hydra#Hydra Theorem.

The following is a sketch of a proof of the generalized version:

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.[citation needed] It can also be applied to Goodstein sequences, although less elegantly.[citation needed]

Hydra function

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\times 2 +4}(5) \approx \{5,5,4,3\} >> \text{Graham's number}\\ \text{Hydra}(5) &>& f_{\omega^{\omega\times 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


Sources

Advertisement