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.

of leaves at each turn, the game will eventually end in finitely many steps: if

can be used to demonstrate that the player will always kill the hydra.

, removing the leaves can never cause the hydra to grow, so the player wins after

, we consider two kinds of moves: those that involve a leaf at a distance less than

from the root, and those that involve a leaf at a distance of exactly

, the induction hypothesis tells us that after finitely many such moves, the player will have no choice but to choose a leaf at depth

No move introduces new nodes at this depth, so this entire process can only repeat up to

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.

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

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).

The growth rate of this function is faster than the standard fast-growing hierarchy, as

alone grows at the rate of the fast-growing hierarchy, and the solution is the nth nesting of

[5] Instead of adding only new leaves, this rule adds duplicates of an entire subtree.

This functions growth rate is massive, equal to

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

At each stage, the player chooses a leaf node

The game ends when the hydra is reduced to a single node.

To obtain a fast-growing function, we can fix

, and so on, and decide on a simple rule for where to cut, say, always choosing the rightmost leaf.

is the number of steps needed for the game to end starting with a path of length

eventually dominates all recursive functions which are provably total in Peano arithmetic, and is itself provably total in

: 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

, which eventually dominates all provably total recursive functions.

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,

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