Hydra game

A simple hydra game can be defined as follows:

• A hydra is a finite rooted tree, which is a connected graph with no cycles and a specific node designated as the root ${\displaystyle R}$ of the tree. In a rooted tree, each node has a single parent (with the exception of the root, which has no parent) and a set of children, as opposed to an unrooted tree where there is no parent-child relationship and we simply refer to edges between nodes.
• The player selects a leaf node ${\displaystyle x}$ from the tree and a natural number ${\displaystyle n}$ during each turn. A leaf node can be defined as a node with no children, or a node of degree 1 which is not ${\displaystyle R}$.
• Remove the leaf node ${\displaystyle x}$. Let ${\displaystyle a}$ be ${\displaystyle x}$'s parent. If ${\displaystyle a=R}$, return to stage 2. Otherwise if ${\displaystyle a\neq R}$, let ${\displaystyle b}$ be the parent of ${\displaystyle a}$. Then create ${\displaystyle n}$ leaf nodes as children of ${\displaystyle b}$ such that the new nodes would appear after any existing children of ${\displaystyle b}$ during a post-order traversal (visually, these new nodes would appear to the right side of any existing children). Then return to stage 2.

Even though the hydra may grow by an unbounded number ${\displaystyle n}$ of leaves at each turn, the game will eventually end in finitely many steps: if ${\displaystyle d}$ is the greatest distance between the root and the leaf, and ${\displaystyle w}$ the number of leaves at this distance, induction on ${\displaystyle d}$ can be used to demonstrate that the player will always kill the hydra. If ${\displaystyle d=1}$, removing the leaves can never cause the hydra to grow, so the player wins after ${\displaystyle w}$ turns. For general ${\displaystyle d}$, we consider two kinds of moves: those that involve a leaf at a distance less than ${\displaystyle d}$ from the root, and those that involve a leaf at a distance of exactly ${\displaystyle d}$. Since moves of the first kind are also identical to moves in a game with depth ${\displaystyle d-1}$, the induction hypothesis tells us that after finitely many such moves, the player will have no choice but to choose a leaf at depth ${\displaystyle d}$. No move introduces new nodes at this depth, so this entire process can only repeat up to ${\displaystyle w}$ times, after which there are no more leaves at depth ${\displaystyle d}$ and the game now has depth (at most) ${\displaystyle d-1}$. Invoking the induction hypothesis again, we find that the player must eventually win overall.

While this shows that the player will win eventually, it can take a very long time. As an example, consider the following algorithm. Pick the rightmost leaf and set ${\displaystyle n=1}$ the first time, ${\displaystyle 2}$ the second time, and so on, always increasing ${\displaystyle n}$ by one. If a hydra has a single ${\displaystyle y}$-length branch, then for ${\displaystyle y=1}$, the hydra is killed in a single step, while it is killed in three steps if ${\displaystyle y=2}$. There are 11 steps required for ${\displaystyle y=3}$. There are 983038 steps required for ${\displaystyle y=4}$. Neither the amount of steps for ${\displaystyle y=5}$ or higher, nor the growth rate of this function, have been calculated, though the growth rate is likely much greater than ${\displaystyle f_{3}(n)}$ in the fast-growing hierarchy.

The Kirby–Paris hydra is defined by altering the fourth rule of the hydra defined above.

4_KP: Assume ${\displaystyle b}$ is the parent of ${\displaystyle a}$ if ${\displaystyle a\neq R}$. Attach ${\displaystyle n}$ copies of the subtree with root ${\displaystyle a}$ to ${\displaystyle b}$ to the right of all other nodes connected to ${\displaystyle b}$. Return to stage 2.[2]

Instead of adding only new leaves, this rule adds duplicates of an entire subtree. Keeping everything else the same, this time ${\displaystyle y=1}$ requires ${\displaystyle 1}$ turn, ${\displaystyle y=2}$ requires ${\displaystyle 3}$ steps, ${\displaystyle y=3}$ requires ${\displaystyle 37}$ steps and ${\displaystyle y=4}$ requires more steps than Graham's number. This functions growth rate is massive, equal to ${\displaystyle f_{\varepsilon _{0}}(n)}$ in the fast-growing hierarchy.

This is not the most powerful hydra. The Buchholz hydra is a more potent hydra.[3] It entails a labelled tree. The root has a unique label (call it ${\displaystyle R}$), and each other node has a label that is either a non-negative integer or ${\displaystyle \omega }$.[4]

1. A hydra is a labelled tree with finite roots. The root should be labelled ${\displaystyle R}$. Label all nodes adjacent to the root ${\displaystyle 0}$ (important to ensure that it always ends) and every other node with a non-negative integer or ${\displaystyle \omega }$.
2. Choose a leaf node ${\displaystyle x}$ and a natural number ${\displaystyle n}$ at each stage.
3. Remove the leaf ${\displaystyle x}$. Let ${\displaystyle a}$ be ${\displaystyle x}$'s parent. Nothing else happens if ${\displaystyle a=R}$. Return to stage 2.
4. If the label of ${\displaystyle x}$ is ${\displaystyle 0}$, Assume ${\displaystyle b}$ is the parent of ${\displaystyle a}$. Attach ${\displaystyle n}$ copies of the subtree with root ${\displaystyle a}$ to ${\displaystyle b}$ to the right of all other nodes connected to ${\displaystyle b}$. Return to stage 2.
5. If x's label is ${\displaystyle \omega }$, replace it with ${\displaystyle n+1}$. Return to stage 2.
6. If the label of ${\displaystyle x}$ is a positive integer ${\displaystyle u}$. go down the tree looking for a node ${\displaystyle c}$ with a label ${\displaystyle <u}$. Such a node exists because all nodes adjacent to the root are labelled ${\displaystyle 0}$. Take a copy of the subtree with root ${\displaystyle c}$. Replace ${\displaystyle x}$ with this subtree. However, relabel ${\displaystyle x}$ (the root of the copy of the subtree) with ${\displaystyle u-1}$. Call the equivalent of ${\displaystyle x}$ in the copied subtree ${\displaystyle x'}$ (so ${\displaystyle x}$ is to ${\displaystyle x'}$ as ${\displaystyle c}$ is to ${\displaystyle x}$), and relabel ${\displaystyle x'}$ it 0. Go back to stage 2.[5]

Surprisingly, even though the hydra can grow enormously taller, this sequence always ends.[6]

For Kirby–Paris hydras, the rules are simple: start with a hydra, which is an unordered unlabelled rooted tree ${\displaystyle T}$. At each stage, the player chooses a leaf node ${\displaystyle c}$ to chop and a non-negative integer ${\displaystyle n}$. If ${\displaystyle c}$ is a child of the root ${\displaystyle r}$, it is removed from the tree and nothing else happens that turn. Otherwise, let ${\displaystyle p}$ be ${\displaystyle c}$'s parent, and ${\displaystyle g}$ be ${\displaystyle p}$'s parent. Remove ${\displaystyle c}$ from the tree, then add ${\displaystyle n}$ copies of the modified ${\displaystyle p}$ as children to ${\displaystyle g}$. The game ends when the hydra is reduced to a single node.

To obtain a fast-growing function, we can fix ${\displaystyle n}$, say, ${\displaystyle n=1}$ at the first step, then ${\displaystyle n=2}$, ${\displaystyle n=3}$, and so on, and decide on a simple rule for where to cut, say, always choosing the rightmost leaf. Then, ${\displaystyle \operatorname {Hydra} (k)}$ is the number of steps needed for the game to end starting with a path of length ${\displaystyle k}$, that is, a linear stack of ${\displaystyle k+1}$ nodes. ${\displaystyle \operatorname {Hydra} (k)}$ eventually dominates all recursive functions which are provably total in Peano arithmetic, and is itself provably total in ${\displaystyle \mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})}$.[7]

This could alternatively expressed using strings of brackets:

• Start with a finite sequence of brackets such as ${\displaystyle (()(()(())((()))))}$.
• Pick an empty pair ${\displaystyle ()}$ and a non-negative integer ${\displaystyle n}$.
• Delete the pair, and if its parent is not the outermost pair, take its parent and append ${\displaystyle n}$ copies of it.

For example, with ${\displaystyle n=3}$, ${\displaystyle (()(()\mathbf {()} ))\implies (()(())(())(())(()))}$. Next is a list of values of ${\displaystyle \operatorname {Hydra} (k)}$:

• ${\displaystyle \operatorname {Hydra} (0)=0}$
• ${\displaystyle \operatorname {Hydra} (1)=1}$
• ${\displaystyle \operatorname {Hydra} (2)=3}$
• ${\displaystyle \operatorname {Hydra} (3)=37}$
• ${\displaystyle \operatorname {Hydra} (4)>f_{\omega \cdot 2+4}(5)\gg {\text{Graham's number}}}$
• ${\displaystyle \operatorname {Hydra} (5)>f_{\omega ^{2+4}}(5)}$
• ${\displaystyle \operatorname {Hydra} (6)>f_{\underbrace {\omega ^{\cdots ^{\omega }}} _{6}}(5)}$

The Buchholz hydra game is a hydra game in mathematical logic, a single player game based on the idea of chopping pieces off a mathematical tree. The hydra game can be used to generate a rapidly growing function ${\displaystyle BH(n)}$, which eventually dominates all provably total recursive functions. It is an extension of Kirby-Paris hydras. What we use to obtain a fast-growing function is the same as Kirby-Paris hydras, but because Buchholz hydras grow not only in width but also in height, ${\displaystyle BH(n)}$ has a much greater growth rate of ${\displaystyle f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)}$:

• ${\displaystyle BH(1)=0}$
• ${\displaystyle BH(2)=1}$
• ${\displaystyle BH(3)<f_{\varepsilon _{0}}(3)}$

This system can also be used to create an ordinal notation for infinite ordinals, e.g. ${\displaystyle \psi _{0}(\Omega _{\omega })=+0(\omega )}$.

• Goodstein's theorem

 This article incorporates text by Komi Amiko available under the CC BY 4.0 license.

• The hydra game
• Hercules and the hydra
• Kill the Mathematical Hydra by PBS Infinite Series