Laaarge numbers, Part II

In our journey for large numbers, we encounter a mythical monster – the Hydra. We will though deal with a well known, more abstract version of it.

Our hydras are just trees, they have a root and heads and will thus look like this:

Image is missing

Hercules has to kill the Hydra by cutting off its heads. However, every time he removes a head, the remaining parent node it was attached to will re-grow several times. If we chop off the indicated head above, the Hydra will re-grow to be

Image is missing

Only the root will not re-grow, so Hercules can remove heads directly attached to the root safely. Can Hercules kill the Hydra? If he is unfortunate, the results will be horrific. If he cuts off the head on the very left, the Hydra will become

Image is missing

But even if he makes good choices, he can expect a hell of a fight. Try it on a piece of paper.

Can the Hydra get overwhelming in size with no chance of ever cutting it down? Let’s code up some fights:

We can represent Hydras as nested lists, for example the first hydra above would be written as

hydra = [ [ [], [ [], [] ] ] ]

How do we fight it? We have to indicate which head to kill, so we can use a path of indices through the Hydra until we reach a head. For example [0, 1, 0] would point to the top-left head which Hercules killed in the example. Now we code the removal of heads

def removehead(hydra, path):

    # Longer path to go? Descend further down
    if len(path) > 2:
        removehead(hydra[path[0]], path[1:])

    # We kill the head, but the parent will re-grow
    elif len(path) == 2:
        parent = hydra[path[0]]
        head = parent[path[1]]
        if head != []:
            raise ValueError("Indicated element is not a head")

        # Remove the head from parent
        del parent[path[1]]

        # Re-grow parent twice

    # We kill a head right at the root, so nothing will re-grow
    elif len(path) == 1:
        head = hydra[path[0]]
        if head != []:
            raise ValueError("Indicated element is not a head")

        del hydra[path[0]]

        raise ValueError("Invalid path")

def copy(hydra):
    return [ copy(child) for child in hydra ]

Let’s try

>>> removehead(hydra,[0,1,0])
>>> hydra
[[[], [[]], [[]], [[]]]]

We can now simulate how long the fight will last. We just need a strategy to select the head we want to kill. At the moment, let’s just always take the leftmost head

def leftmost(hydra):
    if hydra == []:
        return []
        return [0] + leftmost(hydra[0])

Then we can simulate

def hercules(hydra, headstrategy):
    steps = 0
    while hydra != []:
        path = headstrategy(hydra)
        removehead(hydra, path)
        steps += 1

    return steps

>>> hercules(hydra, headstrategy=leftmost)

88000 steps just to kill the tiniest Hydra? Let’s just attach one more head at the end

hydra = [ [ [], [ [], [], [] ] ] ]

and the program won’t be able to kill the thing in acceptable time on my computer. Let’s gather a bit of information on the shape of the hydra in each stage

def size(hydra):
    if hydra == []:
        return 1
        return 1 + sum(size(child) for child in hydra)

def numheads(hydra):
    if hydra == []:
        return 1
        return sum(numheads(child) for child in hydra)

def depth(hydra):
    if hydra == []:
        return 0
        return 1 + max(depth(child) for child in hydra)

def maxdegree(hydra):
    if hydra == []:
        return 0
        return max(len(hydra), max(maxdegree(child) for child in hydra))

and print it

    while hydra != []:
        if steps % 10000 == 0:
            print("STEP %i" % steps)
            print("Size: %i" % size(hydra))
            print("#Heads: %i" % numheads(hydra))
            print("Depth: %i" % depth(hydra))
            print("Max. degree: %i" % maxdegree(hydra))

We get after 100000 steps

Size: 1041575
#Heads: 881450
Depth: 3
Max. degree: 158880

Killing heads can never increase the depth, that’s good. But the size of the thing is enormous, and there is a single node with 158880 children attachted to it. None of these characteristic numbers decreases with each stage.

You cannot lose

The surprising result is: Hercules can not lose against the Hydra. Every strategy will eventually kill the Hydra, but it will take ridiculously long.

The key insight is that by killing any head, we somehow reduce the complexity of the Hydra in a way it can’t make up for it by re-growing a parent whose complexity already has been reduced. The measure of complexity that has to be used goes by the name epsilon-zero, and is not straightforward in any sense. No combination of the characteristics like #Heads, Size etc. will do. The intricate order on Epsilon-zero is recursive and in some sense resembles the nature of the Hydra-game itself.

Knowing that killing the Hydra is always possible in a finite number of steps, we can use the game to give us increadibly fast-growing functions. Which strategy do we use? Why not the worst strategy? But there might be no worst strategy. Start with some Hydra, then strategy 1 could kill it in $10^{10}$ moves, strategy 2 in $10^{20}$, strategy 3 in $10^{30}$ moves and so on. Because every strategy produces new and bigger hydras that we somehow need to cut down, there is no finite set of strategies.

We can show that the above situation cannot happen, which is precisely Kőnig’s lemma. It says

For every game, there is either a longest finite game or there is an infinite game.

Think about it for a second, for games you know. Are there arbitrarily long games? Now, we know that there is no infinite fight against the Hydra, because its complexity gets reduced in every round. So there is a longest fight.

The function “the longest fight against a hydra of size $n$” is our new example for a disgustingly fast-growing function.

Leave a Reply

Your email address will not be published. Required fields are marked *