Hydra game

In mathematics, specifically in graph theory and number theory, a hydra game is a single-player iterative mathematical game played on a mathematical tree called a hydra where, usually, the goal is to cut off the hydra's "heads" while the hydra simultaneously expands itself. Hydra games can be used to generate large numbers or infinite ordinals or prove the strength of certain mathematical theories.^[1]

Unlike their combinatorial counterparts like TREE and SCG, no search is required to compute these fast-growing function values – one must simply keep applying the transformation rule to the tree until the game says to stop.

Introduction[]

A simple hydra game can be defined as follows:

• A hydra is a finite rooted tree, which is a network of points and lines with no loops and a single starting point known as the root. The root is referred to as ${\displaystyle R}$.
• The player selects a leaf node ${\displaystyle x}$ and a natural number ${\displaystyle n}$ at each stage. A leaf node is a point with only one line connected to it that is not the root.
• Remove the leaf ${\displaystyle x}$. Let ${\displaystyle a}$ be ${\displaystyle x}$'s parent. Nothing else happens if ${\displaystyle a=R}$. Return to stage 2.
• If ${\displaystyle a\neq R}$, let ${\displaystyle b}$ be a parent of ${\displaystyle a}$. Attach ${\displaystyle n}$ leaves to ${\displaystyle b}$, to the right of all other nodes attached to ${\displaystyle b}$. Return to stage 2.

Induction can be used to demonstrate that the player will always kill the hydra. Let ${\displaystyle k}$ be the greatest distance between the root and the leaf. If ${\displaystyle k=1}$, removing the leaves has no effect: the hydra will die in a finite amount of time. If ${\displaystyle k=m}$ is true, let ${\displaystyle k=m+1}$ also be true. The player can now continue to remove leaves from a distance of ${\displaystyle m}$ or less, but only for a limited time. After a while, the player will need to take a leaf ${\displaystyle m+1}$ away. Repeat until there are no more leaves less than ${\displaystyle m}$ away. Then remove another leaf ${\displaystyle m+1}$ away, and so on until there are none left. But then, every leaf is ${\displaystyle m}$ or less away. As a result, any finite hydra can be killed.

We can develop an 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.

Kirby–Paris and Buchholz hydras[]

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]

More about KB hydras[]

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}}\approx E[3]3\#\#4\#64}$
• ${\displaystyle \operatorname {Hydra} (5)>f_{\omega ^{2+4}}(5)}$
• ${\displaystyle \operatorname {Hydra} (6)>f_{\underbrace {\omega ^{\cdots ^{\omega }}} _{6}}(5)}$

More about Buchholz hydras[]

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)\approx E[10]3\#\#\#3}$

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

See also[]

• Goodstein's theorem

References[]

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

External links[]

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