Hydra and Hercules is a finite game on rooted trees. Hercules repeatedly removes a terminal vertex, after which the hydra regrows copies of part of the remaining tree according to the turn number. Every play eventually terminates, but the general termination statement for the Kirby-Paris rules is not provable in Peano arithmetic (Kirby and Paris 1982).
Hydra and Hercules
See also
Goodstein's Theorem, Ordinal Number, Peano Arithmetic, Rooted TreeExplore with Wolfram|Alpha
References
Kirby, L. and Paris, J. "Accessible Independence Results for Peano Arithmetic." Bull. London Math. Soc. 14, 285-293, 1982. https://doi.org/10.1112/blms/14.4.285.Cite this as:
Weisstein, Eric W. "Hydra and Hercules." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HydraandHercules.html