In mathematics, especially mathematical logic, graph theory and number theory, the Buchholz hydra game is a type of hydra game, which is 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 recursive functions that are provably total in "
", and the termination of all hydra games is not provably total in
[1] The game is played on a hydra, a finite, rooted connected tree
, with the following properties: If the player decides to remove the top node
is a current turn number, and then transform itself into a new hydra
represent the part of the hydra which remains after
A series of moves is called a strategy.
A strategy is called a winning strategy if, after a finite amount of moves, the hydra reduces to its root.
This always terminates, even though the hydra can get taller by massive amounts.
[1] Buchholz's paper in 1987 showed that the canonical correspondence between a hydra and an infinitary well-founded tree (or the corresponding term in the notation system
associated to Buchholz's function, which does not necessarily belong to the ordinal notation system
), preserves fundamental sequences of choosing the rightmost leaves and the
operation on an infinitary well-founded tree or the
[2] Suppose a tree consists of just one branch with
(The latter expression means taking the tree
By the hydra theorem, this function is well-defined, but its totality cannot be proven in
Hydras grow extremely fast, because the amount of turns required to kill
is larger than Graham's number or even the amount of turns to kill a Kirby-Paris hydra; and
has an entire Kirby-Paris hydra as its branch.
To be precise, its rate of growth is believed to be comparable to
with respect to the unspecified system of fundamental sequences without a proof.
is the Takeuti-Feferman-Buchholz ordinal which measures the strength of
The first two values of the BH function are virtually degenerate:
Similarly to the weak tree function,
[citation needed] The Buchholz hydra eventually surpasses TREE(n) and SCG(n),[citation needed] yet it is likely weaker than loader as well as numbers from finite promise games.
It is possible to make a one-to-one correspondence between some hydras and ordinals.
To convert a tree or subtree to an ordinal: The resulting ordinal expression is only useful if it is in normal form.
Some examples are: This article incorporates text available under the CC BY-SA 3.0 license.