Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

enter image description here

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.

share|improve this question
    
I am trying to understand the property of Goodstein function. I understand it's a total function, but does it make sense to be a choice function? –  Sniper Clown Jan 28 '13 at 6:14
    
A choice function starts with a set $A$ of nonempty sets, and for each $a\in A$ picks an $x\in a$. How does Goodstein function relate to this? –  Andres Caicedo Jan 28 '13 at 6:25
    
@AndresCaicedo I deleted the first part. –  Sniper Clown Jan 28 '13 at 7:06
2  
Ok, I'm still not sure what you have in mind for the quantum game, though there are some interesting variants that perhaps capture some of what you would like, and are proof-theoretically more demanding. See for example madore.org/~david/math/hydra.xhtml and the work of Buchholz. –  Andres Caicedo Jan 28 '13 at 7:20
    
(By the way, other than a metaphor, there is nothing in common between what is discussed in the link you suggest, and the Hydra game of Kirby and Paris.) –  Andres Caicedo Jan 28 '13 at 22:47

1 Answer 1

The probabilistic hydra game has to converge to dead hydra for the same reason, but because of the extremely long possible game play, I would guess that in any reasonable formalization, random variables that measure the length of the game (if provably a function of the gameplay, in Peano arithmetic) do not have finite expected value.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.