Geodesic
Hercules versus Hidden Hydra Helper
Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) no. 4, pp. 731-741 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 
@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
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/

[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