## HydrasThe word “hydra” may invoke an image of a mythical, many-headed
snake. In that case it may surprise you that mathematicians have their
own concept of hydras. You might start by wondering whether a hydra is
an animal or a plant. It may seem like it’s obviously an animal,
but a mathematical hydra is a type of tree! Here is the evaluation for y=3 in bracket notation: (((()))), ((()())), ((())()()), ((())()), ((())), (()()()()()), (()()()()), (()()()), (()()), (()), (). That was only the warm up. The next hydra is far more fearsome, even though it only appears to be a slight extension. The Kirby-Paris hydra only changes rule 4. 4 _{KP}: If a is not R, let b be the parent of a. Attach n copies
of the subtree with root a to b by an edge, to the right of all other
nodes attached to b. Repeat stage 2.This time, it is not just a few leaves being added, it’s copies of an entire subtree! Keeping everything else the same, y = 1
results in 1 step, y = 2 results in 3 steps, y = 3 results in 37 steps,
but y = 4 results in more steps than Graham’s number! The growth
rate is f, which is a power tower of ωs.
However, even if you choose x and n, the Kirby-Paris hydra will eventually
be killed. The proof is complex and requires ordinals._{ε0}This is not the most fearsome hydra. The Buchholz hydra is an even more powerful hydra. It involves a labelled tree. The root has a special label (call it R), and every other node has a label of either a non-negative integer or ω. 1: A hydra is a finite rooted labelled tree. Label the root R. Label all nodes adjacent to the root 0 (important to make sure that it always terminates) and every other node with either a non-negative integer or ω. 2: At each stage, you pick a leaf node x and a natural number n. 3: Cut off the leaf x. Let a be the parent of x. If a = R, nothing else happens. Go back to stage 2. 4: If the label of x is 0, follow the Kirby-Paris rule and then go back to stage 2. 5: If the label of x is ω, relabel x with n+1. Go back to stage 2. 6: The label of x is a positive integer u+1. Go down the tree looking for a node c with a label < u+1. Such a node exists because all nodes adjacent to the root are labelled 0. Take a copy of the subtree with root c. Replace x with this subtree. However, relabel x (the root of the copy of the subtree) with u. Call x’ the equivalent of x in the copied subtree (so x is to x’ as c is to x) and relabel it 0. Go back to stage 2. Remarkably, this always terminates, even though the hydra can get taller by massive amounts! However, it does take a very, very long time. This time, label the root R, the first node 0, and all other nodes ω. For y = 1, it only takes 1 step. For y = 2, it takes many more steps than Graham’s Number or even Kirby-Paris(4)! This can easily be proved as after the 6th step it contains a Kirby-Paris(4) tree as a branch. Its growth rate is at an extremely high ordinal called the Takeuti-Feferman-Buchholz ordinal. ## Related entries•Fast growing hierarchy | ||

Home • Contact |