Hydra game

Last updated December 19, 2024

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.^[1]

Introduction

A simple hydra game can be defined as follows:

A hydra is a finite rooted tree, which is a connected graph with no cycles and a specific node designated as the root $R$ of the tree. In a rooted tree, each node has a single parent (with the exception of the root, which has no parent) and a set of children, as opposed to an unrooted tree where there is no parent-child relationship and we simply refer to edges between nodes.
The player selects a leaf node $x$ from the tree and a natural number $n$ during each turn. A leaf node can be defined as a node with no children, or a node of degree 1 which is not $R$ .
Remove the leaf node $x$ . Let $a$ be $x$ 's parent. If $a=R$ , return to stage 2. Otherwise if $a\neq R$ , let $b$ be the parent of $a$ . Then create $n$ leaf nodes as children of $b$ such that the new nodes would appear after any existing children of $b$ during a post-order traversal (visually, these new nodes would appear to the right side of any existing children). Then return to stage 2.

Even though the hydra may grow by an unbounded number $n$ of leaves at each turn, the game will eventually end in finitely many steps: if $d$ is the greatest distance between the root and the leaf, and $w$ the number of leaves at this distance, induction on $d$ can be used to demonstrate that the player will always kill the hydra. If $d=1$ , removing the leaves can never cause the hydra to grow, so the player wins after $w$ turns. For general $d$ , we consider two kinds of moves: those that involve a leaf at a distance less than $d$ from the root, and those that involve a leaf at a distance of exactly $d$ . Since moves of the first kind are also identical to moves in a game with depth $d-1$ , the induction hypothesis tells us that after finitely many such moves, the player will have no choice but to choose a leaf at depth $d$ . No move introduces new nodes at this depth, so this entire process can only repeat up to $w$ times, after which there are no more leaves at depth $d$ and the game now has depth (at most) $d-1$ . Invoking the induction hypothesis again, we find that the player must eventually win overall.

While this shows that the player will win eventually, it can take a very long time. As an example, consider the following algorithm. Pick the rightmost leaf (i.e., the newest leaf which will be on the level closest to the root) and set $n=1$ the first time, $2$ the second time, and so on, always increasing $n$ by one. If a hydra has a single $y$ -length branch, then for $y=1$ , the hydra is killed in a single step, while it is killed in three steps if $y=2$ . There are 11 steps required for $y=3$ . There are 1114111 steps required for $y=4$ .^[2] $y=5$ has been calculated exactly.^[3] Let $F(x)=2^{x}\cdot (x+2)-1$ and $F^{n}(x)$ to be $F$ nested n times. Then $HYDRA(5)=2\cdot F^{F^{2}(3)+1}(F^{2}(3)+1)+1=2\cdot F^{22539988369408}(22539988369408)+1$ .

All steps of the simple hydra game with y = 3 SimpleHydraGameY3.svg — All steps of the simple hydra game with y = 3

General Solution

The general solution to the hydra game is as follows:^[4]

Let $F_{i}(x)$ denote the number of steps required to decrement a head of depth n when the heads closer to the roots are all singular (no further "right" branches).

Then $F_{i+1}(x)=F_{i}^{x}(x+1)$ and $F_{1}(x)=2\cdot (x+1)-1=2x+1$ .

The answer to $hydra(n)$ is: $F_{1}(F_{2}(F_{3}(\ldots F_{n-1}(F_{n}(1))\ldots )))$

The growth rate of this function is faster than the standard fast-growing hierarchy, as $F_{i}(x)$ alone grows at the rate of the fast-growing hierarchy, and the solution is the nth nesting of $F_{i}(x)$ .

Kirby–Paris and Buchholz Hydras

The Kirby–Paris hydra is defined by altering the fourth rule of the hydra defined above.

4_KP: Assume $b$ is the parent of $a$ if $a\neq R$ . Attach $n$ copies of the subtree with root $a$ to $b$ to the right of all other nodes connected to $b$ . Return to stage 2.^[5]

Instead of adding only new leaves, this rule adds duplicates of an entire subtree. Keeping everything else the same, this time $y=1$ requires $1$ turn, $y=2$ requires $3$ steps, $y=3$ requires $37$ steps and $y=4$ requires more steps than Graham's number. This functions growth rate is massive, equal to $f_{\varepsilon _{0}}(n)$ in the fast-growing hierarchy.

This is not the most powerful hydra. The Buchholz hydra is a more potent hydra.^[6] It entails a labelled tree. The root has a unique label (call it $R$ ), and each other node has a label that is either a non-negative integer or $\omega$ .^[7]

A hydra is a labelled tree with finite roots. The root should be labelled $R$ . Label all nodes adjacent to the root $0$ (important to ensure that it always ends) and every other node with a non-negative integer or $\omega$ .
Choose a leaf node $x$ and a natural number $n$ at each stage.
Remove the leaf $x$ . Let $a$ be $x$ 's parent. Nothing else happens if $a=R$ . Return to stage 2.
If the label of $x$ is $0$ , Assume $b$ is the parent of $a$ . Attach $n$ copies of the subtree with root $a$ to $b$ to the right of all other nodes connected to $b$ . Return to stage 2.
If x's label is $\omega$ , replace it with $n+1$ . Return to stage 2.
If the label of $x$ is a positive integer $u$ . go down the tree looking for a node $c$ with a label $<u$ . Such a node exists because all nodes adjacent to the root are labelled $0$ . Take a copy of the subtree with root $c$ . Replace $x$ with this subtree. However, relabel $x$ (the root of the copy of the subtree) with $u-1$ . Call the equivalent of $x$ in the copied subtree $x'$ (so $x$ is to $x'$ as $c$ is to $x$ ), and relabel it $(x')$ 0. Go back to stage 2.^[8]

Surprisingly, even though the hydra can grow enormously taller, this sequence always ends.^[9]

More about KP hydras

For Kirby–Paris hydras, the rules are simple: start with a hydra, which is an unordered unlabelled rooted tree $T$ . At each stage, the player chooses a leaf node $c$ to chop and a non-negative integer $n$ . If $c$ is a child of the root $r$ , it is removed from the tree and nothing else happens that turn. Otherwise, let $p$ be $c$ 's parent, and $g$ be $p$ 's parent. Remove $c$ from the tree, then add $n$ copies of the modified $p$ as children to $g$ . The game ends when the hydra is reduced to a single node.

To obtain a fast-growing function, we can fix $n$ , say, $n=1$ at the first step, then $n=2$ , $n=3$ , and so on, and decide on a simple rule for where to cut, say, always choosing the rightmost leaf. Then, $\operatorname {Hydra} (k)$ is the number of steps needed for the game to end starting with a path of length $k$ , that is, a linear stack of $k+1$ nodes. $\operatorname {Hydra} (k)$ eventually dominates all recursive functions which are provably total in Peano arithmetic, and is itself provably total in $\mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})$ .^[10]

This could alternatively expressed using strings of brackets:

Start with a finite sequence of brackets such as $(()(()(())((()))))$ .
Pick an empty pair $()$ and a non-negative integer $n$ .
Delete the pair, and if its parent is not the outermost pair, take its parent and append $n$ copies of it.

For example, with $n=3$ , $(()(()\mathbf {()} ))\implies (()(())(())(())(()))$ . Next is a list of values of $\operatorname {Hydra} (k)$ :

$\operatorname {Hydra} (0)=0$
$\operatorname {Hydra} (1)=1$
$\operatorname {Hydra} (2)=3$
$\operatorname {Hydra} (3)=37$
$\operatorname {Hydra} (4)>f_{\omega \cdot 2+4}(5)\gg {\text{Graham's number}}$
$\operatorname {Hydra} (5)>f_{\omega ^{2+4}}(5)$
$\operatorname {Hydra} (6)>f_{\underbrace {\omega ^{\cdots ^{\omega }}} _{6}}(5)$

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 $BH(n)$ , 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, $BH(n)$ has a much greater growth rate of $f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)$ :

$BH(1)=0$
$BH(2)=1$
$BH(3)<f_{\varepsilon _{0}}(3)$

This system can also be used to create an ordinal notation for infinite ordinals, e.g. $\psi _{0}(\Omega _{\omega })=+0(\omega )$ .

Related Research Articles

<span class="mw-page-title-main">AVL tree</span> Self-balancing binary search tree

In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take $O(log n)$ time in both the average and worst cases, where $is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.$

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is linear with respect to the height of the tree.

In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. That is, it is a k-ary tree with $k = 2$ . A recursive definition using set theory is that a binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root.

A random variable is a mathematical formalization of a quantity or object which depends on random events. The term 'random variable' in its mathematical definition refers to neither randomness nor variability but instead is a mathematical function in which

In mathematics, mathematical physics and the theory of stochastic processes, a harmonic function is a twice continuously differentiable function $where U is an open subset of ⁠ ⁠ that satisfies Laplace's equation, that is, everywhere on U . This is usually written as or$

Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.

<span class="mw-page-title-main">Jensen's inequality</span> Theorem of convex functions

In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906, building on an earlier proof of the same inequality for doubly-differentiable functions by Otto Hölder in 1889. Given its generality, the inequality appears in many forms depending on the context, some of which are presented below. In its simplest form the inequality states that the convex transformation of a mean is less than or equal to the mean applied after convex transformation.

In set theory, a tree is a partially ordered set (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well-ordered by the relation <. Frequently trees are assumed to have only one root (i.e. minimal element), as the typical questions investigated in this field are easily reduced to questions about single-rooted trees.

In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is generative recursion, which may lack a definite "direction" inherent in corecursion and recursion.

In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Arne Andersson in 1989 and again by Igal Galperin and Ronald L. Rivest in 1993. It provides worst-case lookup time and $amortized insertion and deletion time.$

In set theory, the Baire space is the set of all infinite sequences of natural numbers with a certain topology, called the product topology. This space is commonly used in descriptive set theory, to the extent that its elements are often called "reals". It is denoted by $, or ω ω, or by the symbol or sometimes by ω ω .$

In mathematics, a $π$ -system on a set $is a collection of certain subsets of such that$

The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. The theorem was first published by J. Howard Redfield in 1927. In 1937 it was independently rediscovered by George Pólya, who then greatly popularized the result by applying it to many counting problems, in particular to the enumeration of chemical compounds.

In mathematics – specifically, in the theory of stochastic processes – Doob's martingale convergence theorems are a collection of results on the limits of supermartingales, named after the American mathematician Joseph L. Doob. Informally, the martingale convergence theorem typically refers to the result that any supermartingale satisfying a certain boundedness condition must converge. One may think of supermartingales as the random variable analogues of non-increasing sequences; from this perspective, the martingale convergence theorem is a random variable analogue of the monotone convergence theorem, which states that any bounded monotone sequence converges. There are symmetric results for submartingales, which are analogous to non-decreasing sequences.

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic.

In computer science, frequent subtree mining is the problem of finding all patterns in a given database whose support is over a given threshold. It is a more general form of the maximum agreement subtree problem.

In mathematics, the exponential response formula (ERF), also known as exponential response and complex replacement, is a method used to find a particular solution of a non-homogeneous linear ordinary differential equation of any order. The exponential response formula is applicable to non-homogeneous linear ordinary differential equations with constant coefficients if the function is polynomial, sinusoidal, exponential or the combination of the three. The general solution of a non-homogeneous linear ordinary differential equation is a superposition of the general solution of the associated homogeneous ODE and a particular solution to the non-homogeneous ODE. Alternative methods for solving ordinary differential equations of higher order are method of undetermined coefficients and method of variation of parameters.

In computer science, the list-labeling problem involves maintaining a totally ordered set S supporting the following operations:

In functional analysis, every C^*-algebra is isomorphic to a subalgebra of the C^*-algebra $of bounded linear operators on some Hilbert space This article describes the spectral theory of closed normal subalgebras of . A subalgebra of is called normal if it is commutative and closed under the operation: for all, we have and that .$

In mathematics, especially mathematical logic, graph theory and number theory, the Buchholz hydra game is a type of hydra game, which is 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, $, which eventually dominates all recursive functions that are provably total in " ", and the termination of all hydra games is not provably total in .$

References

↑ Kirby, Laurie; Paris, Jeff. "Accessible independence results for Peano arithmetic" (PDF). Department of applied logic. Retrieved 2021-09-04.
↑ "The Hydra Game - Numberphile". 18 April 2024.
↑ "Hydra(5)".
↑ "The Hydra Game Solved".
↑ "Hydras". agnijomaths.com. Retrieved 2021-09-05.
↑ Hamano, Masahiro; Okada, Mitsuhiro (1995). "A Relationship among Gentzen's Proof-Reduction, Kirby-Paris) Hydra Game, and Buchholz's Hydra Game (Preliminary Report)*" (PDF). Research Institute for Mathematical Sciences, Kyoto University. Retrieved 2021-09-04.
↑ Ketonen, Jussi; Solovay, Robert (1981). "Rapidly Growing Ramsey Functions". Annals of Mathematics. 113 (2): 267–314. doi:10.2307/2006985. ISSN 0003-486X. JSTOR 2006985.
↑ Buchholz, Wilfried (1984-11-27). "An independence result for Π11 - CA + BI" (PDF). Ludwig-Maximilians-University of Munich. Retrieved 2021-09-04.
↑ Hamano, Masahiro; Okada, Mitsuhiro (1998-03-01). "A direct independence proof of Buchholz's Hydra Game on finite labeled trees". Archive for Mathematical Logic. 37 (2): 67–89. doi:10.1007/s001530050084. ISSN 1432-0665. S2CID 40113368.
↑ Carlucci, Lorenzo (2003-05-07). "A new proof-theoretic proof of the independence of Kirby–Paris' Hydra Theorem". Theoretical Computer Science. 300 (1–3): 365–378. doi:10.1016/S0304-3975(02)00332-8. ISSN 0304-3975.

This article incorporates text by Komi Amiko available under the CC BY 4.0 license.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Kirby, Laurie; Paris, Jeff. "Accessible independence results for Peano arithmetic" (PDF). Department of applied logic. Retrieved 2021-09-04.

[2] "The Hydra Game - Numberphile". 18 April 2024.

[3] "Hydra(5)".

[4] "The Hydra Game Solved".

[5] "Hydras". agnijomaths.com. Retrieved 2021-09-05.

[6] Hamano, Masahiro; Okada, Mitsuhiro (1995). "A Relationship among Gentzen's Proof-Reduction, Kirby-Paris) Hydra Game, and Buchholz's Hydra Game (Preliminary Report)*" (PDF). Research Institute for Mathematical Sciences, Kyoto University. Retrieved 2021-09-04.

[7] Ketonen, Jussi; Solovay, Robert (1981). "Rapidly Growing Ramsey Functions". Annals of Mathematics. 113 (2): 267–314. doi:10.2307/2006985. ISSN 0003-486X. JSTOR 2006985.

[8] Buchholz, Wilfried (1984-11-27). "An independence result for Π11 - CA + BI" (PDF). Ludwig-Maximilians-University of Munich. Retrieved 2021-09-04.

[9] Hamano, Masahiro; Okada, Mitsuhiro (1998-03-01). "A direct independence proof of Buchholz's Hydra Game on finite labeled trees". Archive for Mathematical Logic. 37 (2): 67–89. doi:10.1007/s001530050084. ISSN 1432-0665. S2CID 40113368.

[10] Carlucci, Lorenzo (2003-05-07). "A new proof-theoretic proof of the independence of Kirby–Paris' Hydra Theorem". Theoretical Computer Science. 300 (1–3): 365–378. doi:10.1016/S0304-3975(02)00332-8. ISSN 0304-3975.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]