Hydras

The 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!

The first hydra has no name as far as I know, but it is an ideal starting point for beginners. Here are the rules.

1: A hydra is a finite rooted tree. This means that it is simply a network of points and lines with no loops and one particular starting point known as the root. Call the root R.
2: At each stage, you pick a leaf node x and a natural number n. A leaf node is a point with only one line attached that is not the root.         
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 a is not R, let b be the parent of a. Attach n leaves to b, to the right of all other nodes attached to b. Repeat stage 2.

It can be proven that you will always kill the hydra (reduce it to a root with no leaves). It can be proved using induction. Let k be the longest distance from the root to the leaf. If k = 1, removing leaves does nothing so the hydra will be killed in finite time. If it is true for k = m, let k = m+1. Now we can keep removing leaves m or less away but only for a finite amount of time. After a while you will have to remove a leaf m+1 away. Repeat until there are no leaves m or less away. Then you must remove another leaf m+1 away and so on until there are none. But then every leaf is m or less away. Thus any finite hydra will be killed.

A hydra can be represented by bracket notation. The first ( represents the root node. From there, all subsequent (s represent going up from the node you’re on to its leftmost branch not yet visited while ) represents going down a branch.

We can make an algorithm. Always pick the rightmost leaf and set n = 1 the first time, 2 the second, and so on, always incrementing n by 1. Now imagine certain hydras. Suppose a hydra has a single branch of length y. For y = 1, the hydra is killed in 1 step. For y = 2, it is killed in 3 steps. For y = 3, 11 steps are needed. For y = 4, 983038 steps are required. I have no data for y = 5 or beyond, or the growth rate of this truly rapidly-growing function, although I expect it is much more than f₃ (roughly tetrational). I found this lower bound by examining what happens if it is not always the rightmost leaf that gets deleted, but some other leaf of my choice, as defined by a different algorithm in some cases.

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_ε0, 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.
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