Geodesic
Hercules versus Hidden Hydra Helper
Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) no. 4, pp. 731-741

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR   Zbl

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.
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.
Classification : 03B25, 03F30, 05C05, 90D46, 90D99
Keywords: rooted tree; unprovability; Kirby--Paris Theorem 
Matoušek, Jiří; Loebl, Martin. Hercules versus Hidden Hydra Helper. Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) no. 4, pp. 731-741. http://geodesic.mathdoc.fr/item/CMUC_1991_32_4_a15/
@article{CMUC_1991_32_4_a15,
     author = {Matou\v{s}ek, Ji\v{r}{\'\i} and Loebl, Martin},
     title = {Hercules versus {Hidden} {Hydra} {Helper}},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {731--741},
     year = {1991},
     volume = {32},
     number = {4},
     mrnumber = {1159820},
     zbl = {0763.05029},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1991_32_4_a15/}
}
TY  - JOUR
AU  - Matoušek, Jiří
AU  - Loebl, Martin
TI  - Hercules versus Hidden Hydra Helper
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1991
SP  - 731
EP  - 741
VL  - 32
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMUC_1991_32_4_a15/
LA  - en
ID  - CMUC_1991_32_4_a15
ER  - 
%0 Journal Article
%A Matoušek, Jiří
%A Loebl, Martin
%T Hercules versus Hidden Hydra Helper
%J Commentationes Mathematicae Universitatis Carolinae
%D 1991
%P 731-741
%V 32
%N 4
%U http://geodesic.mathdoc.fr/item/CMUC_1991_32_4_a15/
%G en
%F CMUC_1991_32_4_a15

[1] Kirby L., Paris J.: Accessible independence results for Peano Arithmetic. Bulletin of the London Math. Soc 14, 1982. | MR | Zbl

[2] Loebl M.: Hercules and Hydra, the game on rooted finite trees. Comment. Math. Univ. Carolinae 26 (1985), 259-267. | MR

[3] Loebl M.: Hercules and Hydra. Comment. Math. Univ. Carolinae 29 (1988), 85-95. | MR | Zbl

[4] Buchholz W., Wainer S.: Provably computable functions and the fast growing hierarchy. in: {Logic and Combinatorics}, Contemporary Mathematics, vol. 65, AMS 1986. | MR | Zbl