# Buchholz hydra

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, $BH(n)$, which eventually dominates all recursive functions that are provably total in "${\textrm {ID}}_{\nu }$", and the termination of all hydra games is not provably total in ${\textrm {}\Pi _{1}^{1}{\textrm {-CA)+BI}}$.

## Rules

The game is played on a hydra, a finite, rooted connected tree $A$, with the following properties:
* The root of $A$ has a special label, usually denoted $+$.
* Any other node of $A$ has a label $\nu \leq \omega$.
* All nodes directly above the root of $A$ have a label $0$.
If the player decides to remove the top node $\sigma$ of $A$, the hydra will then choose an arbitrary $n\in \mathbb {N}$, where $n$ is a current turn number, and then transform itself into a new hydra $A(\sigma ,n)$ as follows. Let $\tau$ represent the parent of $\sigma$, and let $A^{-}$ represent the part of the hydra which remains after $\sigma$ has been removed. The definition of $A(\sigma ,n)$ depends on the label of $\sigma$:
* If the label of $\sigma$ is 0 and $\tau$ is the root of $A$, then $A(\sigma ,n)$ = $A^{-}$.
* If the label of $\sigma$ is 0 but $\tau$ is not the root of $A$, $n$ copies of $\tau$ and all its children are made, and edges between them and $\tau$'s parent are added. This new tree is $A(\sigma ,n)$.
* If the label of $\sigma$ is $u$ for some $u\in \mathbb {N}$, let $\varepsilon$ be the first node below $\sigma$ that has a label $v<u$. Define $B$ as the subtree obtained by starting with $A_{\varepsilon }$ and replacing the label of $\varepsilon$ with $u-1$ and $\sigma$ with 0. $A(\sigma ,n)$ is then obtained by taking $A$ and replacing $\sigma$ with $B$. In this case, the value of $n$ does not matter.
* If the label of $\sigma$ is $\omega$, $A(\sigma ,n)$ is obtained by replacing the label of $\sigma$ with $n+1$.
If $\sigma$ is the rightmost head of $A$, $A(n)$ is written. 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.

## Hydra theorem

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 $T$ associated to Buchholz's function, which does not necessarily belong to the ordinal notation system $OT\subset T$), preserves fundamental sequences of choosing the rightmost leaves and the $(n)$ operation on an infinitary well-founded tree or the $[n]$ operation on the corresponding term in $T$.
The hydra theorem for Buchholz hydra, stating that there are no losing strategies for any hydra, is unprovable in ${\mathsf {\Pi _{1}^{1}-CA+BI}}$.

## BH(n)

Suppose a tree consists of just one branch with $x$ nodes, labelled $+,0,\omega ,...,\omega$. Call such a tree $R^{n}$. It cannot be proven in ${\mathsf {\Pi _{1}^{1}-CA+BI}}$ that for all $x$, there exists $k$ such that $R_{x}(1)(2)(3)...(k)$ is a winning strategy. (The latter expression means taking the tree $R_{x}$, then transforming it with $n=1$, then $n=2$, then $n=3$, etc. up to $n=k$.)
Define $BH(x)$ as the smallest $k$ such that $R_{x}(1)(2)(3)...(k)$ as defined above is a winning strategy. By the hydra theorem, this function is well-defined, but its totality cannot be proven in ${\mathsf {\Pi _{1}^{1}-CA+BI}}$. Hydras grow extremely fast, because the amount of turns required to kill $R_{x}(1)(2)$ is larger than Graham's number or even the amount of turns to kill a Kirby-Paris hydra; and $R_{x}(1)(2)(3)(4)(5)(6)$ has an entire Kirby-Paris hydra as its branch. To be precise, its rate of growth is believed to be comparable to $f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(x)$ with respect to the unspecified system of fundamental sequences without a proof. Here, $\psi _{0}$ denotes Buchholz's function, and $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$ is the Takeuti-Feferman-Buchholz ordinal which measures the strength of ${\mathsf {\Pi _{1}^{1}-CA+BI}}$.
The first two values of the BH function are virtually degenerate: $BH(1)=0$ and $BH(2)=1$. Similarly to the weak tree function, $BH(3)$ is very large, but less so.
The Buchholz hydra eventually surpasses TREE(n) and SCG(n), yet it is likely weaker than loader as well as numbers from finite promise games.

## Analysis

It is possible to make a one-to-one correspondence between some hydras and ordinals. To convert a tree or subtree to an ordinal:
* Inductively convert all the immediate children of the node to ordinals.
* Add up those child ordinals. If there were no children, this will be 0.
* If the label of the node is not +, apply $\psi _{\alpha }$, where $\alpha$ is the label of the node, and $\psi$ is Buchholz's function.
The resulting ordinal expression is only useful if it is in normal form. Some examples are:
Conversion :
| Hydra | Ordinal |
| $+$ | $0$ |
| $+(0)$ | $\psi _{0}(0)=1$ |
| $+(0)(0)$ | $2$ |
| $+(0(0))$ | $\psi _{0}(1)=\omega$ |
| $+(0(0))(0)$ | $\omega +1$ |
| $+(0(0))(0(0))$ | $\omega \cdot 2$ |
| $+(0(0)(0))$ | $\omega ^{2}$ |
| $+(0(0(0)))$ | $\omega ^{\omega }$ |
| $+(0(1))$ | $\varepsilon _{0}$ |
| $+(0(1)(1))$ | $\varepsilon _{1}$ |
| $+(0(1(0)))$ | $\varepsilon _{\omega }$ |
| $+(0(1(1)))$ | $\zeta _{0}$ |
| $+(0(1(1(1))))$ | $\Gamma _{0}$ |
| $+(0(1(1(1(0)))))$ | SVO |
| $+(0(1(1(1(1)))))$ | LVO |
| $+(0(2))$ | BHO |
| $+(0(\omega ))$ | BO |