Hydra game
In mathematics, specifically in graph theory and number theory, a hydra game is a single-player iterative mathematical game played on a mathematical tree called a "hydra" where, usually, the goal is to cut off the hydra's "heads" while the hydra simultaneously expands itself. Hydra games can be used to generate large numbers or infinite ordinals or prove the strength of certain mathematical theories. Unlike their combinatorial counterparts like TREE and SCG, no search is required to compute these fast-growing function values – one must simply keep applying the transformation rule to the tree until the game  says to stop. Introduction. A simple hydra game can be defined as follows: Induction can be used to demonstrate that the player will always kill the hydra. Let formula_14 be the greatest distance between the root and the leaf. If formula_15, removing the leaves has no effect: the hydra will die in a finite amount of time. If formula_16 is true, let formula_17 also be true. The player can now continue to remove leaves from a distance of formula_18 or less, but only for a limited time. After a while, the player will need to take a leaf formula_19 away . Repeat until there are no more leaves less than formula_18 away. Then remove another leaf formula_19 away, and so on until there are none left. But then, every leaf is formula_18 or less away. As a result, any finite hydra can be killed. We can develop an algorithm. Pick the rightmost leaf and set formula_23 the first time, formula_24 the second time, and so on, always increasing formula_3 by one. If a hydra has a single formula_26-length branch, then for formula_27, the hydra is killed in a single step, while it is killed in three steps if formula_28. There  are 11 steps required for formula_29. There are 983038 steps required for formula_30. Neither the amount of steps for formula_31 or higher, nor the growth rate of this function, have been calculated, though the growth rate is likely much greater than formula_32 in the fast-growing hierarchy. Kirby–Paris and Buchholz hydras. The Kirby–Paris hydra is defined by altering the fourth rule of the hydra defined above. 4: Assume formula_9 is the parent of formula_5 if formula_8. Attach formula_3 copies of the subtree with root formula_5 to formula_9 to the right of all other nodes connected to formula_9. Return  to stage 2. Instead of adding only new leaves, this rule adds duplicates of an entire subtree. Keeping everything else the same, this time formula_27 requires formula_41 turn, formula_42 requires formula_43 steps, formula_44 requires formula_45 steps and formula_46 requires more steps than Graham's number. This functions growth rate is "massive", equal to formula_47 in the fast-growing hierarchy. This is not the most powerful hydra. The Buchholz hydra is a more potent hydra. It entails a labelled tree. The root has a unique label (call it formula_1), and each other node has a label that is either a non -negative integer or formula_49. Surprisingly, even though the hydra can grow enormously taller, this sequence always ends. More about KB hydras. For Kirby–Paris hydras, the rules are simple: start with a hydra, which is an unordered unlabelled rooted tree formula_85. At each stage, the player chooses a leaf node formula_71 to chop and a non-negative integer formula_3. If formula_71 is a child of the root formula_89, it is removed from the tree and nothing else happens that turn. Otherwise, let formula_90 be formula_71's parent, and formula_92 be formula_90's parent. Remove formula_71 from the tree, then add  formula_3 copies of the modified formula_90 as children to formula_92. The game ends when the hydra is reduced to a single node. To obtain a fast-growing function, we can fix formula_3, say, formula_99 at the first step, then formula_100, formula_101, and so on, and decide on a simple rule for where to cut, say, always choosing the rightmost leaf. Then, formula_102 is the number of steps needed for the game to end starting with a path of length formula_14, that is, a linear stack of formula_104 nodes. formula_102 eventually dominates all recursive functions which are provably total in Peano  arithmetic, and is itself provably total in formula_106. This could alternatively expressed using strings of brackets: For example, with formula_101, formula_112. Next is a list of values of formula_102: More about Buchholz hydras. The Buchholz hydra game is a hydra game in mathematical logic, a single player game based on the idea of chopping pieces off a mathematical tree. The hydra game can be used to generate a rapidly growing function formula_121, which eventually dominates all provably total recursive functions. It is an extension of Kirby-Paris hydras. What we use to obtain a fast-growing function is the same  as Kirby-Paris hydras, but because Buchholz hydras grow not only in width but also in height, formula_121 has a much greater growth rate of formula_123: This system can also be used to create an ordinal notation for infinite ordinals, e.g. formula_127.