[FOM] Hydra games?

[Mitch Harris]

> From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] 
> On Behalf Of Peter Smith
> Sent: Sunday, May 23, 2010 1:51 PM
> 
> Ok, there's the foundations-significant Kirby/Paris hydra battle, where we

> can show that Hercules always wins, by a transfinite induction up to 
> epsilon_0

> Now, there must be lots of other hydra games -- maybe some of them even a 
> bit interesting! -- that terminate (or at least terminate on best play) 
> with a win for Hercules, and can be shown to do so by inductions along 
> smaller ordinals.

I know of one: a billiard table with numbered balls. You can take off any
ball, but I can put back on any number of balls of lesser number (and they
don't all have to be the same number). The goal is for you to clear the
table and me to prevent you. The relevant ordinal is omega^omega.


> Does anyone happen to know if there's a discussion out there of examples
of 
> such shorter games?

I got this from Nachum Dershowitz (I was a grad student of his). I can't
remember if it started with him; he uses Hercules-Hydra examples in his
termination work, but I can't remember if he discussed in a paper the
billiard table example. Martin Gardner wrote a Mathematical Games article in
the late seventies which discussed ordinals and termination; there might be
other warm-up examples there or in Nachum's papers.

Mitch Harris