Buchholz Hydra

In mathematical logic, specifically in 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 "$\mathsf$", and is itself provably total in "$\mathsf$ "transfinite induction with respect to TFB".

Rules

The game is played on a ''hydra'', a finite, rooted connected mathematical 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 chops off a head/leaf (i.e. the top node) $\sigma$ of $A$, the hydra will then choose an arbitrary $n \in \N$ (e.g. the current turn number), and then transform itself into a new hydra $A(\sigma, n)$ like so. Let $\tau$ represent the parent of $\sigma$, and let $A^-$ represent the part of the hydra which remains after $\sigma$ has been chopped off. 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$, we make $n$ copies of $\tau$ and all its children and attach them all to $\tau$'s parent. This new tree is $A(\sigma, n)$.
* If the label of $\sigma$ is $u$ for some $u \in \N$, then we label the first node below $\sigma$ with label $v < u$ as $\varepsilon$. $B$ is then 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 simply obtained by replacing the label of $\sigma$ with $n + 1$.

If $\sigma$ is the rightmost head of $A$, we write simply $A(n)$. A series of moves is called a strategy, and a strategy is called a winning strategy if, after a (finite) amount of moves, nothing is left of the hydra except its root. It has proven that this always terminates, even though the hydra can get taller by massive amounts. However, it does take a significant amount of time.

Hydra theorem

Buchholz's paper in 1987 showed the canonical correspondence from a hydra to 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, i.e. the strategy to choose the rightmost leaves and the $(n)$ operation on an infinitary well-founded tree (or the  /math> 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$.

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$ 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$. 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_(x)$ with respect to unspecified system of fundamental sequences without a proof. Here, $\psi_0$ denotes Buchholz's function, and $\psi_0(\varepsilon_)$ is the Takeuti-Feferman-Buchholz ordinal which measures the strength of $\mathsf$.

The first two values of the BH function are virtually degenerate: $BH(1) = 0$ and $BH(2) = 1$. Similarly to the tree function, $BH(3)$ is very large, but not extremely.

The Buchholz hydra eventually surpasses TREE(n) and SCG(n), yet it is likely weaker than loader.c as well as numbers from finite promise games.

Analysis

It is possible to make 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:

References

*
*
*
*
*
*
*
*
*

__FORCETOC__

{{Large numbers

Trees (graph theory)
Mathematical games
Large numbers
Ordinal numbers
Theorems in discrete mathematics