Hercules versus Hidden Hydra Helper

Jiří Matoušek; Martin Loebl

Commentationes Mathematicae Universitatis Carolinae (1991)

  • Volume: 32, Issue: 4, page 731-741
  • ISSN: 0010-2628

Abstract

top
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 2 Hidden Hydra Helper has a strategy for making the game long.

How to cite

top

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 -

References

top
  1. Kirby L., Paris J., Accessible independence results for Peano Arithmetic, Bulletin of the London Math. Soc 14, 1982. Zbl0501.03017MR0663480
  2. Loebl M., Hercules and Hydra, the game on rooted finite trees, Comment. Math. Univ. Carolinae 26 (1985), 259-267. (1985) MR0803922
  3. Loebl M., Hercules and Hydra, Comment. Math. Univ. Carolinae 29 (1988), 85-95. (1988) Zbl0666.05024MR0937552
  4. Buchholz W., Wainer S., Provably computable functions and the fast growing hierarchy, in: {Logic and Combinatorics}, Contemporary Mathematics, vol. 65, AMS 1986. Zbl0635.03056MR0891248

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.