The hydra game

Today I lectured about the Hydra game by Laurence Kirby and Jeff Paris (Accessible Independence Results for Peano Arithmetic, Kirby and Paris, Bull. London Math. Soc. 1982; 14: 285-293). For the occasion I implemented the game in Java. I am publishing the code for anyone who wants to play, or use it for teaching.

About the game

A hydra is a finite tree, with a root at the bottom. The object of the game is to cut down the hydra to its root. At each step, you can cut off one of the heads, after which the hydra grows new heads according to the following rules:

  • If you cut off a head growing out of the root, the hydra does not grow any new heads.
  • Suppose you cut off a head like this:

    Delete the head and its neck. Descend down by 1 from the node at which the neck was attached. Look at the subtree growing from the connection through which you just descended. Pick a natural number, say 3, and grow that many copies of that subtree, like this:

My program grows $n$ copies at step $n$ of the game, which is one possible variant of the game. There are spoilers ahead, so before you read on you should play the game with the Hydra applet (your browser must support Java) and try to win. Is it possible to win? How should you play to win?

Here is a surprising fact:

Theorem 1: You cannot lose!

The proof uses ordinal numbers. To each hydra we assign an ordinal number:

  • A head gets the number $0$.
  • Suppose a node $x$ has sub-hydras $H_1, \ldots, H_n$ growing from it. To each sub-hydra we assign its ordinal recursively and order the ordinals in descending order: $\alpha_1 \geq \alpha_2 \geq \ldots \geq \alpha_n$. The ordinal assigned to the node $x$ is $\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$. For example, the ordinal corresponding to the hydra from the first picture above is $\omega^{\omega^3 + 1} + 1$. The hydra in the second picture gets the ordinal $\omega^{\omega^2 \cdot 4 + 1} + 1$.
  • By chopping off a head we strictly decrease the ordinal. Because there are no infinite strictly descending sequences of ordinals, the hydra will eventually die, no matter how you chop off heads.

But Theorem 1 is not the punchline. The punchline is this:

Theorem 2 (Kirby and Paris): Any proof technique that proves Theorem 1 is strong enough to prove that Peano arithmetic is consistent.

Consistency of Peano arithmetic is Hilbert’s second problem, which was solved by Gentzen in 1936.

Download the program

The program is written in Java and is available freely under the BSD License. You may:

18 thoughts on “The hydra game

  1. Hi,

    Cool game. But I think it has a bug. You don’t seem to eliminate a head attached to the root when picked, so that those “root heads” get replicated when you subsequently pick a non root head to eliminate.

    If I have this to start:

    O  Y  X 
    \ /  /  
     O  /  
     | / 
     O
    

    And eliminate the X, and then the Y, it’s as if I never eliminated the X at all.

    Or perhaps I don’t understand the game…

    John.

  2. I think there’s something you don’t understand. If you first cut off X (assuming in your picture that X grows from the root), then X disappears, of course. After that, if you cut of Y, X will not magically reappear. Which bit of the text is unclear to you?

  3. The ordinals you provide for the two pictures have lost all the formatting for exponentiation, and thus are very confusing. Also, there’s a small error:

    first pic: ω^(ω^3 + 1) + 1
    2nd pic: ω^((ω^2)*4 + 1) + 1

    Your error was that the four was on the wrong side of the ω^2.

  4. @Peter: I see them fine on my Firefox, what platform are you using? I fixed the problem with multiplication by 4 from the wrong side, thank you for spotting it.

  5. @Bo: I think it’s ok. The head itself gets a 0, but because it is growing out of a lower node, we turn that into $\omega^0 = 1$. So, the only way to get $0$ is to have just one head without any necks, in other words the root. For example, if we had one head growing out of the root we would assign $0$ to the head, and then $\omega^0 = 1$ to the whole thing.

  6. I can’t get the java applet to work in Opera or Firefox, and the program didn’t work as a standalone either. (I followed the command-line instructions and got a “class not found” type of error. I do have the JRE installed.) Any chance you can help? I’d like to use it for a talk I’m giving in two days.

    Scott

  7. It works for me under Chrome 17.0. on MacOS. At a minimum you’d have to tell me what OS you’re using, which version of Opera/Firefox you’re using, can you run any other applets on the internet, what version of JRE you installed, and what version of Java your browser is using.

  8. I got it to work. Note for other Ubuntu users–make sure you have the icedtea6-plugin installed for the web applet to work.

  9. The .jar file seems to be missing a manifest. I had to run it like this:

    java -cp ~/Downloads/hydra.jar hydra.HydraWindow

    The META-INF/MANIFEST.MF should have a line like:

    Main-Class: hydra.HydraWindow

  10. Thanks, Andrej, and thanks, Brendan – your instructions work for me (on OSX)

  11. I’m not sure I understand this. It starts with size 9 by default, I changed it to 3 (I body with 2 heads) to make an original hydra. If I click on one head, instead of making 2 extra heads grow in it’s place (making it 3 heads and one body) like the hydra thing goes, it switches to 1 head and 1 body. Also, why does it have multiple bodies if you start at 9? I thought the hydra always had 1 body, and heads never grew heads. Very confused.

Leave a Reply

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

75 + = 76

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>