Английская Википедия:Buchholz hydra

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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 of a mathematical tree. The hydra game can be used to generate a rapidly growing function, <math>BH(n)</math>, which eventually dominates all recursive functions that are provably total in "<math>\textrm{ID}_{\nu}</math>", and the termination of all hydra games is not provably total in <math>\textrm{(}\Pi_1^1\textrm{-CA)+BI}</math>.

Rules

The game is played on a hydra, a finite, rooted connected tree <math>A</math>, with the following properties:

• The root of <math>A</math> has a special label, usually denoted <math>+</math>.
• Any other node of <math>A</math> has a label <math>\nu \leq \omega</math>.
• All nodes directly above the root of <math>A</math> have a label <math>0</math>.

If the player decides to remove the top node <math>\sigma</math> of <math>A</math>, the hydra will then choose an arbitrary <math>n \in \N</math>, where <math>n</math> is a current turn number, and then transform itself into a new hydra <math>A(\sigma, n)</math> as follows. Let <math>\tau</math> represent the parent of <math>\sigma</math>, and let <math>A^-</math> represent the part of the hydra which remains after <math>\sigma</math> has been removed. The definition of <math>A(\sigma, n)</math> depends on the label of <math>\sigma</math>:

• If the label of <math>\sigma</math> is 0 and <math>\tau</math> is the root of <math>A</math>, then <math>A(\sigma, n)</math> = <math>A^-</math>.
• If the label of <math>\sigma</math> is 0 but <math>\tau</math> is not the root of <math>A</math>, <math>n</math> copies of <math>\tau</math> and all its children are made, and edges between them and <math>\tau</math>'s parent are added. This new tree is <math>A(\sigma, n)</math>.
• If the label of <math>\sigma</math> is <math>u</math> for some <math>u \in \N</math>, then the first node below <math>\sigma</math> is labelled <math>v < u</math> as <math>\varepsilon</math>. <math>B</math> is then the subtree obtained by starting with <math>A_\varepsilon</math> and replacing the label of <math>\varepsilon</math> with <math>u - 1</math> and <math>\sigma</math> with 0. <math>A(\sigma, n)</math> is then obtained by taking <math>A</math> and replacing <math>\sigma</math> with <math>B</math>. In this case, the value of <math>n</math> does not matter.
• If the label of <math>\sigma</math> is <math>\omega</math>, <math>A(\sigma, n)</math> is obtained by replacing the label of <math>\sigma</math> with <math>n + 1</math>.

If <math>\sigma</math> is the rightmost head of <math>A</math>, <math>A(n)</math> is written. A series of moves is called a strategy. A strategy is called a winning strategy if, after a finite amount of moves, the hydra reduces to its root. It has been proven that this always terminatesШаблон:Fact, even though the hydra can get taller by massive amounts.

Hydra theorem

Buchholz's paper in 1987 showed that the canonical correspondence between a hydra and an infinitary well-founded tree (or the corresponding term in the notation system <math>T</math> associated to Buchholz's function, which does not necessarily belong to the ordinal notation system <math>OT \subset T</math>), preserves fundamental sequences of choosing the rightmost leaves and the <math>(n)</math> operation on an infinitary well-founded tree or the <math>[n]</math> operation on the corresponding term in <math>T</math>.

The hydra theorem for Buchholz hydra, stating that there are no losing strategies for any hydra, is unprovable in <math>\mathsf{\Pi^1_1 - CA + BI}</math>.

BH(n)

Suppose a tree consists of just one branch with <math>x</math> nodes, labelled <math>+, 0, \omega, ..., \omega</math>. Call such a tree <math>R^n</math>. It cannotШаблон:Fact be proven in <math>\mathsf{\Pi^1_1 - CA + BI}</math> that for all <math>x</math>, there exists <math>k</math> such that <math>R_x(1)(2)(3)...(k)</math> is a winning strategy. (The latter expression means taking the tree <math>R_x</math>, then transforming it with <math>n=1</math>, then <math>n=2</math>, then <math>n=3</math>, etc. up to <math>n=k</math>.)

Define <math>BH(x)</math> as the smallest <math>k</math> such that <math>R_x(1)(2)(3)...(k)</math> as defined above is a winning strategy. By the hydra theorem, this function is well-defined, but its totality cannot be proven in <math>\mathsf{\Pi^1_1 - CA + BI}</math>. Hydras grow extremely fast, because the amount of turns required to kill <math>R_x(1)(2)</math> is larger than Graham's number or even the amount of turns to kill a Kirby-Paris hydra; and <math>R_x(1)(2)(3)(4)(5)(6)</math> has an entire Kirby-Paris hydra as its branch. To be precise, its rate of growth is believed to be comparable to <math>f_{\psi_0(\varepsilon_{\Omega_\omega + 1})}(x)</math> with respect to the unspecified system of fundamental sequences without a proof. Here, <math>\psi_0</math> denotes Buchholz's function, and <math>\psi_0(\varepsilon_{\Omega_\omega + 1})</math> is the Takeuti-Feferman-Buchholz ordinal which measures the strength of <math>\mathsf{\Pi^1_1 - CA + BI}</math>.

The first two values of the BH function are virtually degenerate: <math>BH(1) = 0</math> and <math>BH(2) = 1</math>. Similarly to the weak tree function, <math>BH(3)</math> is very large, but less so.Шаблон:Fact

The Buchholz hydra eventually surpasses TREE(n) and SCG(n),Шаблон:Citation needed yet it is likely weaker than loader as well as numbers from finite promise games.

Analysis

It is possible to make a one-to-one correspondence between some hydras and ordinalsШаблон:Fact. To convert a tree or subtree to an ordinal:

• Inductively convert all the immediate children of the node to ordinals.
• Add up those child ordinals. If there were no children, this will be 0.
• If the label of the node is not +, apply <math>\psi_\alpha</math>, where <math>\alpha</math> is the label of the node, and <math>\psi</math> is Buchholz's function.

The resulting ordinal expression is only useful if it is in normal form. Some examples are:

Conversion

Hydra	Ordinal
<math>+</math>	<math>0</math>
<math>+(0)</math>	<math>\psi_0(0) = 1</math>
<math>+(0)(0)</math>	<math>2</math>
<math>+(0(0))</math>	<math>\psi_0(1) = \omega</math>
<math>+(0(0))(0)</math>	<math>\omega + 1</math>
<math>+(0(0))(0(0))</math>	<math>\omega \cdot 2</math>
<math>+(0(0)(0))</math>	<math>\omega^2</math>
<math>+(0(0(0)))</math>	<math>\omega^\omega</math>
<math>+(0(1))</math>	<math>\varepsilon_0</math>
<math>+(0(1)(1))</math>	<math>\varepsilon_1</math>
<math>+(0(1(0)))</math>	<math>\varepsilon_\omega</math>
<math>+(0(1(1)))</math>	<math>\zeta_0</math>
<math>+(0(1(1(1))))</math>	<math>\Gamma_0</math>
<math>+(0(1(1(1(0)))))</math>	SVO
<math>+(0(1(1(1(1)))))</math>	LVO
<math>+(0(2))</math>	BHO
<math>+(0(\omega))</math>	BO

References

• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Citation
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite web

Шаблон:Large numbers