- 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
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
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
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.
\text{Hydra}(6) is about the size of dulatri and gingulus, very large numbers.
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
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.