Buchholz hydra explained

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 "

rm{ID}_\nu

", and the termination of all hydra games is not provably total in

	1rm{-CA)+BI}
rm{(}\Pi
	1

Rules

, with the following properties:

The root of

has a special label, usually denoted

Any other node of

has a label

\nu\leq\omega

All nodes directly above the root of

have a label

If the player decides to remove the top node

\sigma

, the hydra will then choose an arbitrary

n\in\N

, where

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

, then

A(\sigma,n)

A^-

If the label of

\sigma

is 0 but

\tau

is not the root of

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

for some

u\in\N

, let

\varepsilon

be the first node below

\sigma

that has a label

v<u

. Define

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

and replacing

\sigma

with

. In this case, the value of

does not matter.

If the label of

\sigma

\omega

A(\sigma,n)

is obtained by replacing the label of

\sigma

with

n+1

\sigma

is the rightmost head of

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

associated to Buchholz's function, which does not necessarily belong to the ordinal notation system

OT\subsetT

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

The hydra theorem for Buchholz hydra, stating that there are no losing strategies for any hydra, is unprovable in

	1
\Pi		-CA+BI
	1

BH(n)

Suppose a tree consists of just one branch with

nodes, labelled

+,0,\omega,...,\omega

. Call such a tree

Rⁿ

. It cannot be proven in

	1
\Pi		-CA+BI
	1

that for all

, there exists

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

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

	1
\Pi		-CA+BI
	1

. 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

\psi


	\Omega_\omega+1

)

0(\varepsilon

(x)

with respect to the unspecified system of fundamental sequences without a proof. Here,

\psi₀

denotes Buchholz's function, and

\psi_{0(\varepsilon}


	\Omega_\omega+1

)

is the Takeuti-Feferman-Buchholz ordinal which measures the strength of

	1
\Pi		-CA+BI
	1

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:

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Buchholz hydra".

Conversion!Hydra!Ordinal
+	0
+(0)	\psi₀₍₀₎=1
+(0)(0)	2
+(0(0))	\psi₀₍₁₎=\omega
+(0(0))(0)	\omega+1
+(0(0))(0(0))	\omega ⋅ 2
+(0(0)(0))	\omega²
+(0(0(0)))	\omega^\omega
+(0(1))	\varepsilon₀
+(0(1)(1))	\varepsilon₁
+(0(1(0)))	\varepsilon_\omega
+(0(1(1)))	\zeta₀
+(0(1(1(1))))	\Gamma₀
+(0(1(1(1(0)))))	SVO
+(0(1(1(1(1)))))	LVO
+(0(2))	BHO
+(0(\omega))	BO