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 connected graph with no cycles and a specific node designated as the root $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 $x$ from the tree and a natural number $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 $R$ .
Remove the leaf node $x$ . Let $a$ be $x$ 's parent. If $a=R$ , return to stage 2. Otherwise if $a\neq R$ , let $b$ be the parent of $a$ . Then create $n$ leaf nodes as children of $b$ such that the new nodes would appear after any existing children of $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 $n$ of leaves at each turn, the game will eventually end in finitely many steps: if $d$ is the greatest distance between the root and the leaf, and $w$ the number of leaves at this distance, induction on $d$ can be used to demonstrate that the player will always kill the hydra. If $d=1$ , removing the leaves can never cause the hydra to grow, so the player wins after $w$ turns. For general $d$ , we consider two kinds of moves: those that involve a leaf at a distance less than $d$ from the root, and those that involve a leaf at a distance of exactly $d$ . Since moves of the first kind are also identical to moves in a game with depth $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 $d$ . No move introduces new nodes at this depth, so this entire process can only repeat up to $w$ times, after which there are no more leaves at depth $d$ and the game now has depth (at most) $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 (ie the newest leaf which will be on the level closest to the root) and set $n=1$ the first time, $2$ the second time, and so on, always increasing $n$ by one. If a hydra has a single $y$ -length branch, then for $y=1$ , the hydra is killed in a single step, while it is killed in three steps if $y=2$ . There are 11 steps required for $y=3$ . There are 1114111 steps required for $y=4$ .^[2] $y=5$ has been calculated exactly.^[3] Let $F(x)=2^{x}\cdot (x+2)-1$ and $F^{n}(x)$ to be $F$ nested n times. Then $HYDRA(5)=2\cdot F^{F^{2}(3)+1}(F^{2}(3)+1)+1=2\cdot F^{22539988369408}(22539988369408)+1$ .

All steps of the simple hydra game with y = 3

General Solution

The general solution to the hydra game is as follows:^[4]

Let $F_{i}(x)$ denote the number of steps required to decrement a head of depth n when the heads closer to the roots are all singular (no further "right" branches).

Then $F_{i+1}(x)=F_{i}^{x}(x+1)$ and $F_{1}(x)=2\cdot (x+1)-1=2x+1$ .

The answer to $hydra(n)$ is: $F_{1}(F_{2}(F_{3}(\ldots F_{n-1}(F_{n}(1))\ldots )))$

The growth rate of this function is faster than the standard fast-growing hierarchy, as $F_{i}(x)$ alone grows at the rate of the fast-growing hierarchy, and the solution is the nth nesting of $F_{i}(x)$ .

Kirby–Paris and Buchholz hydras

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

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

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

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

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

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

More about KP hydras

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

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

This could alternatively expressed using strings of brackets:

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

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

$\operatorname {Hydra} (0)=0$
$\operatorname {Hydra} (1)=1$
$\operatorname {Hydra} (2)=3$
$\operatorname {Hydra} (3)=37$
$\operatorname {Hydra} (4)>f_{\omega \cdot 2+4}(5)\gg {\text{Graham's number}}$
$\operatorname {Hydra} (5)>f_{\omega ^{2+4}}(5)$
$\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 $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, $BH(n)$ has a much greater growth rate of $f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)$ :

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

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

References

^ Kirby, Laurie; Paris, Jeff. "Accessible independence results for Peano arithmetic" (PDF). Department of applied logic. Retrieved 2021-09-04.
^ "The Hydra Game - Numberphile". 18 April 2024.
^ "Hydra(5)".
^ "The Hydra Game Solved".
^ "Hydras". agnijomaths.com. Retrieved 2021-09-05.
^ Hamano, Masahiro; Okada, Mitsuhiro (1995). "A Relationship among Gentzen's Proof-Reduction, Kirby-Paris) Hydra Game, and Buchholz's Hydra Game (Preliminary Report)*" (PDF). Research Institute for Mathematical Sciences, Kyoto University. Retrieved 2021-09-04.
^ Ketonen, Jussi; Solovay, Robert (1981). "Rapidly Growing Ramsey Functions". Annals of Mathematics. 113 (2): 267–314. doi:10.2307/2006985. ISSN 0003-486X. JSTOR 2006985.
^ Buchholz, Wilfried (1984-11-27). "An independence result for Π11 - CA + BI" (PDF). Ludwig-Maximilians-University of Munich. Retrieved 2021-09-04.
^ Hamano, Masahiro; Okada, Mitsuhiro (1998-03-01). "A direct independence proof of Buchholz's Hydra Game on finite labeled trees". Archive for Mathematical Logic. 37 (2): 67–89. doi:10.1007/s001530050084. ISSN 1432-0665. S2CID 40113368.
^ Carlucci, Lorenzo (2003-05-07). "A new proof-theoretic proof of the independence of Kirby–Paris' Hydra Theorem". Theoretical Computer Science. 300 (1–3): 365–378. doi:10.1016/S0304-3975(02)00332-8. ISSN 0304-3975.

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

External links

[1] Kirby, Laurie; Paris, Jeff. "Accessible independence results for Peano arithmetic" (PDF). Department of applied logic. Retrieved 2021-09-04.

[2] "The Hydra Game - Numberphile". 18 April 2024.

[3] "Hydra(5)".

[4] "The Hydra Game Solved".

[5] "Hydras". agnijomaths.com. Retrieved 2021-09-05.

[6] Hamano, Masahiro; Okada, Mitsuhiro (1995). "A Relationship among Gentzen's Proof-Reduction, Kirby-Paris) Hydra Game, and Buchholz's Hydra Game (Preliminary Report)*" (PDF). Research Institute for Mathematical Sciences, Kyoto University. Retrieved 2021-09-04.

[7] Ketonen, Jussi; Solovay, Robert (1981). "Rapidly Growing Ramsey Functions". Annals of Mathematics. 113 (2): 267–314. doi:10.2307/2006985. ISSN 0003-486X. JSTOR 2006985.

[8] Buchholz, Wilfried (1984-11-27). "An independence result for Π11 - CA + BI" (PDF). Ludwig-Maximilians-University of Munich. Retrieved 2021-09-04.

[9] Hamano, Masahiro; Okada, Mitsuhiro (1998-03-01). "A direct independence proof of Buchholz's Hydra Game on finite labeled trees". Archive for Mathematical Logic. 37 (2): 67–89. doi:10.1007/s001530050084. ISSN 1432-0665. S2CID 40113368.

[10] Carlucci, Lorenzo (2003-05-07). "A new proof-theoretic proof of the independence of Kirby–Paris' Hydra Theorem". Theoretical Computer Science. 300 (1–3): 365–378. doi:10.1016/S0304-3975(02)00332-8. ISSN 0304-3975.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]