Wiki Googologie
Wiki Googologie
Voir aussi: Hydre de Buchholz

Le jeu de l'hydre Kirby-Paris est un jeu à un joueur qui se joue sur un arbre et qui peut durer un très grand nombre de tours.[1] Il donne lieu à une fonction Hydra(n) qui domine finalement toutes les fonctions récursives qui sont provablement totales en arithmétique de Peano, et qui est elle-même provablement totale en PA + " est bien ordonnée", et le jeu est également lié aux arbres de preuve-réduction de Gentzen.[2]

Le jeu est proche de vers de Beklemishev.


The game is played as follows:

  • We start with a finite rooted tree T. Call its root r.
  • The player picks a leaf vertex of the tree and a natural number n. Call the leaf a and its parent b:
    1. a is deleted from T.
    2. If b = r, nothing happens. Otherwise, let c be the parent of b. Consider the subtree consisting of b and all its children; copy this subtree n times. Attach all these copies to c.

This can be expressed equivalently using strings of parentheses:

  • Start with a finite sequence of matched parentheses such as (()(()(())((())))).
  • Pick an empty pair () and a natural number n.
    1. Delete it.
    2. If its parent is not the outermost pair, take its parent and append n copies of it.

For example, at step 3 we can transform (()(()())) into (()(())(())(())(())).

The player keeps picking leaves and n's and chopping off hydra heads. He wins when the hydra is reduced to a root node.

Hydra theorem

We define a strategy on T as a sequence of leaves and values of n that continues as long as the game does. A winning strategy is one that eventually defeats the hydra, and a losing strategy is one that does not.

Some strategies are obviously winning strategies. Repeatedly setting n = 0 ensures that the hydra never grows back, for instance. But many strategies (especially for large n) can cause hydras to grow very rapidly, raising the question: can the player ever lose by allowing the hydra to grow indefinitely?

The answer is no. The player always wins and there are no losing strategies for any hydra. This is called hydra theorem. Kirby and Paris, who introduced the hydra game first, showed the hydra theorem in the case that n is equal to the number of rounds of the game. It is especially called Kirby-Paris hydra theorem.

The generalized version of the theorem is a corollary of Kirby-Paris hydra theorem. The following is a sketch of a proof of the generalized version:

Proof: We assign an ordinal to each possible tree, defining () = 0 and (H1H2...Hn) = \(\omega^{H_1} + \omega^{H_2} + \ldots + \omega^{H_n}\) where \(H_1 \geq H_2 \geq \ldots \geq H_n\). (This ignores the orders of nodes, but order does not affect the hydra theorem.) It can be shown that removing a leaf strictly decreases the hydra H regardless of the value of n:

  • If the leaf node we select is a child of the root node, the result is H - 1, which is strictly smaller than H.
  • If the leaf node we select is a child of node \(J = \omega^{K+1}\), then chopping it results in \(\omega^Kn\), which is strictly smaller than J for finite n.

Since the hydra's value always decreases, its ordinal will reach 0 in a finite amount of time. //

Hydra function

Often, the number of steps required to defeat the hydra is very large. Since there are so many parameters at work here, we will simplify things using a few conventions:

  • Each hydra is a path of length k, that is, a chain of k + 1 nodes.
  • The strategy always picks the rightmost node using n = 1, then n = 2, then n = 3, etc. until the game ends.

Using these hydras and strategies, define \(\text{Hydra}(k)\) as the number of turns needed to win the game. Then

  • Hydra}(0) = 0
  • Hydra}(1) = 1
  • Hydra}(2) = 3
  • Hydra}(3) = 37
  • Hydra}(4) > >> nombre de Graham
  • Hydra}(5) >

In general, \(f_{\omega^{\omega^{\cdots^{\omega2+4}}}}(6) > \text{Hydra}(n) > f_{\omega^{\omega^{\cdots^{\omega2+4}}}}(5) > X \uparrow\uparrow (n-4) \&\ 5\), where are \(n-3\) copies of \(\omega\) in each tower. Hydra(n) eventually dominates all functions provably recursive in Peano arithmetic, and it can be approximated with the function \(f_{\varepsilon_0}\). In particular, \(\text{Hydra} >^* f_\alpha\) for all \(\alpha < \varepsilon_0\), but \(\text{Hydra} <^* f_{\varepsilon_0 + 1}\). This puts the hydra function on par with la suite de Goodstein.

External links