L. Kirby and J. Paris introduced the Hercules and Hydra game on rooted trees as a natural example of an undecidable statement in Peano Arithmetic. One can show that Hercules has a ``short'' strategy (he wins in a primitively recursive number of moves) and also a ``long'' strategy (the finiteness of the game cannot be proved in Peano Arithmetic). We investigate the conflict of the ``short'' and ``long'' intentions (a problem suggested by J. Ne{\v s}et{\v r}il). After each move of Hercules (trying to kill Hydra fast) there follow $k$ moves of Hidden Hydra Helper (making the same type of moves as Hercules but trying to keep Hydra alive as long as possible). We prove that for $k=1$ Hercules can make the game short, while for $k\geq 2$ Hidden Hydra Helper has a strategy for making the game long.
@article{118453,
author = {Ji\v r\'\i\ Matou\v sek and Martin Loebl},
title = {Hercules versus Hidden Hydra Helper},
journal = {Commentationes Mathematicae Universitatis Carolinae},
volume = {32},
year = {1991},
pages = {731-741},
zbl = {0763.05029},
mrnumber = {1159820},
language = {en},
url = {http://dml.mathdoc.fr/item/118453}
}
Matoušek, Jiří; Loebl, Martin. Hercules versus Hidden Hydra Helper. Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) pp. 731-741. http://gdmltest.u-ga.fr/item/118453/
Accessible independence results for Peano Arithmetic, Bulletin of the London Math. Soc 14, 1982. | MR 0663480 | Zbl 0501.03017
Hercules and Hydra, the game on rooted finite trees, Comment. Math. Univ. Carolinae 26 (1985), 259-267. (1985) | MR 0803922
Hercules and Hydra, Comment. Math. Univ. Carolinae 29 (1988), 85-95. (1988) | MR 0937552 | Zbl 0666.05024
Provably computable functions and the fast growing hierarchy, in: {Logic and Combinatorics}, Contemporary Mathematics, vol. 65, AMS 1986. | MR 0891248 | Zbl 0635.03056