Hercules versus Hidden Hydra Helper

Matoušek, Jiří, and Loebl, Martin. "Hercules versus Hidden Hydra Helper." Commentationes Mathematicae Universitatis Carolinae 32.4 (1991): 731-741. <http://eudml.org/doc/247291>.

@article{Matoušek1991,
abstract = {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šetř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\ge 2$ Hidden Hydra Helper has a strategy for making the game long.},
author = {Matoušek, Jiří, Loebl, Martin},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {rooted tree; unprovability; Kirby--Paris Theorem; Hercules and Hydra game; rooted tree; unprovability; Kirby-Paris theorem},
language = {eng},
number = {4},
pages = {731-741},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Hercules versus Hidden Hydra Helper},
url = {http://eudml.org/doc/247291},
volume = {32},
year = {1991},
}

TY - JOUR
AU - Matoušek, Jiří
AU - Loebl, Martin
TI - Hercules versus Hidden Hydra Helper
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1991
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 32
IS - 4
SP - 731
EP - 741
AB - 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šetř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\ge 2$ Hidden Hydra Helper has a strategy for making the game long.
LA - eng
KW - rooted tree; unprovability; Kirby--Paris Theorem; Hercules and Hydra game; rooted tree; unprovability; Kirby-Paris theorem
UR - http://eudml.org/doc/247291
ER -