| Title:
|
Hercules versus Hidden Hydra Helper (English) |
| Author:
|
Matoušek, Jiří |
| Author:
|
Loebl, Martin |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
32 |
| Issue:
|
4 |
| Year:
|
1991 |
| Pages:
|
731-741 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
rooted tree |
| Keyword:
|
unprovability |
| Keyword:
|
Kirby--Paris Theorem |
| MSC:
|
03B25 |
| MSC:
|
03F30 |
| MSC:
|
05C05 |
| MSC:
|
90D46 |
| MSC:
|
90D99 |
| idZBL:
|
Zbl 0763.05029 |
| idMR:
|
MR1159820 |
| . |
| Date available:
|
2009-01-08T17:48:41Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118453 |
| . |
| Reference:
|
[1] Kirby L., Paris J.: Accessible independence results for Peano Arithmetic.Bulletin of the London Math. Soc 14, 1982. Zbl 0501.03017, MR 0663480 |
| Reference:
|
[2] Loebl M.: Hercules and Hydra, the game on rooted finite trees.Comment. Math. Univ. Carolinae 26 (1985), 259-267. MR 0803922 |
| Reference:
|
[3] Loebl M.: Hercules and Hydra.Comment. Math. Univ. Carolinae 29 (1988), 85-95. Zbl 0666.05024, MR 0937552 |
| Reference:
|
[4] Buchholz W., Wainer S.: Provably computable functions and the fast growing hierarchy.in: {Logic and Combinatorics}, Contemporary Mathematics, vol. 65, AMS 1986. Zbl 0635.03056, MR 0891248 |
| . |
