Hydra game explained
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
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
from the tree and a natural number
during each turn. A leaf node can be defined as a node with no children, or a node of degree 1 which is not
.
. Let
be
's parent. If
, return to stage 2. Otherwise if
, let
be the parent of
. Then create
leaf nodes as children of
such that the new nodes would appear after any existing children of
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
of leaves at each turn, the game will eventually end in finitely many steps: if
is the greatest distance between the root and the leaf, and
the number of leaves at this distance,
induction on
can be used to demonstrate that the player will always kill the hydra. If
, removing the leaves can never cause the hydra to grow, so the player wins after
turns. For general
, 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
. Since moves of the first kind are also identical to moves in a game with depth
, 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
times, after which there are no more leaves at depth
and the game now has depth (at most)
. 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
the first time,
the second time, and so on, always increasing
by one. If a hydra has a single
-length branch, then for
, the hydra is killed in a single step, while it is killed in three steps if
. There are 11 steps required for
. There are 1114111 steps required for
.
[2]
has been calculated exactly.
[3] Let
and
to be
nested n times. Then
HYDRA(5)=2 ⋅
(F2(3)+1)+1=2 ⋅ F22539988369408(22539988369408)+1
.
General Solution
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).
Then
and
.
The answer to
is:
F1(F2(F3(\ldotsFn-1(Fn(1))\ldots)))
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
.
Kirby–Paris and Buchholz hydras
The Kirby–Paris hydra is defined by altering the fourth rule of the hydra defined above.
4KP: Assume
is the parent of
if
. Attach
copies of the subtree with root
to
to the right of all other nodes connected to
. 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
requires
turn,
requires
steps,
requires
steps and
requires more steps than
Graham's number. This functions growth rate is
massive, equal to
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
), and each other node has a label that is either a non-negative integer or
.
[7] - A hydra is a labelled tree with finite roots. The root should be labelled
. Label all nodes adjacent to the root
(important to ensure that it always ends) and every other node with a non-negative integer or
.
- Choose a leaf node
and a natural number
at each stage.
- Remove the leaf
. Let
be
's parent. Nothing else happens if
. Return to stage 2.
- If the label of
is
, Assume
is the parent of
. Attach
copies of the subtree with root
to
to the right of all other nodes connected to
. Return to stage 2.
- If x's label is
, replace it with
. Return to stage 2.
- If the label of
is a positive integer
. go down the tree looking for a node
with a label
. Such a node exists because all nodes adjacent to the root are labelled
. Take a copy of the subtree with root
. Replace
with this subtree. However, relabel
(the root of the copy of the subtree) with
. Call the equivalent of
in the copied subtree
(so
is to
as
is to
), and relabel it
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
. At each stage, the player chooses a leaf node
to chop and a non-negative integer
. If
is a child of the root
, it is removed from the tree and nothing else happens that turn. Otherwise, let
be
's parent, and
be
's parent. Remove
from the tree, then add
copies of the modified
as children to
. The game ends when the hydra is reduced to a single node.
To obtain a fast-growing function, we can fix
, say,
at the first step, then
,
, and so on, and decide on a simple rule for where to cut, say, always choosing the rightmost leaf. Then,
is the number of steps needed for the game to end starting with a path of length
, that is, a linear stack of
nodes.
eventually dominates all recursive functions which are provably total in Peano arithmetic, and is itself provably total in
PA+(\varepsilon0iswell-ordered)
.
[10] This could alternatively expressed using strings of brackets:
- Start with a finite sequence of brackets such as
.
and a non-negative integer
.
- Delete the pair, and if its parent is not the outermost pair, take its parent and append
copies of it.
For example, with
,
. Next is a list of values of
:
\operatorname{Hydra}(0)=0
\operatorname{Hydra}(1)=1
\operatorname{Hydra}(2)=3
\operatorname{Hydra}(3)=37
\operatorname{Hydra}(4)>f\omega(5)\ggGraham'snumber
\operatorname{Hydra}(5)>
(5)
\operatorname{Hydra}(6)>
6}(5)
More about Buchholz hydras
See main article: Buchholz hydra. 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. 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,
has a much greater growth rate of
:
This system can also be used to create an ordinal notation for infinite ordinals, e.g.
\psi0(\Omega\omega)=+0(\omega)
.
See also
External links
Notes and References
- Web site: Kirby. Laurie. Paris. Jeff. Accessible independence results for Peano arithmetic. 2021-09-04. Department of applied logic.
- https://www.reddit.com/r/BradyHaran/comments/1c6z1t4/the_hydra_game_numberphile/
- https://cal.vin/p/hydra5
- https://li.cal.vin/p/the-hydra-game-solved
- Web site: Hydras. 2021-09-05. agnijomaths.com.
- Web site: Hamano. Masahiro. Okada. Mitsuhiro. 1995. A Relationship among Gentzen's Proof-Reduction, Kirby-Paris) Hydra Game, and Buchholz's Hydra Game (Preliminary Report)*. 2021-09-04. Research Institute for Mathematical Sciences, Kyoto University.
- Ketonen. Jussi. Solovay. Robert. 1981. Rapidly Growing Ramsey Functions. Annals of Mathematics. 113. 2. 267–314. 10.2307/2006985. 2006985. 0003-486X.
- Web site: Buchholz. Wilfried. 1984-11-27. An independence result for Π11 - CA + BI. 2021-09-04. Ludwig-Maximilians-University of Munich.
- Hamano. Masahiro. Okada. Mitsuhiro. 1998-03-01. A direct independence proof of Buchholz's Hydra Game on finite labeled trees. Archive for Mathematical Logic. en. 37. 2. 67–89. 10.1007/s001530050084. 40113368. 1432-0665.
- 2003-05-07. A new proof-theoretic proof of the independence of Kirby–Paris' Hydra Theorem. Theoretical Computer Science. en. 300. 1–3. 365–378. 10.1016/S0304-3975(02)00332-8. 0304-3975. Carlucci. Lorenzo.