Goodstein's theorem is not provable in Peano Arithmetic showed by Kirby and Harrington in 1982 [Wolfram Mathworld].
Any reference of a "quantum" hydra game where a head can remain in a state of superposition?
I only found this folio of Matthew Leifer online.
Background:
Laurence Kirby's homepage talks the following algorithm to solve the Hydra game.
An algorithm for T is as follows: starting from the root, we travel "up" the tree in such a way that, having reached a node, we travel to the node immediately above it which has minimal assigned ordinal among all the nodes immediately above it. (If more than one of them has minimal ordinal we choose, say, the leftmost.) Eventually we reach a top node and the head it is attached to is the one to chop off.
Or as Andrej Bauer writes:
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.
