ヒドラゲーム

Hydra(3) = 37 の時の膨張する (((()))) の木。

ブーフホルツのヒドラ も参照して下さい。

ヒドラゲームはターン数がとても大きく成りうる一人プレイのゲームである。

準備

ルールの説明の前にヒドラゲームで使われる用語の定義を行う。

(単純)グラフとは、次の条件を満たす集合\(V,E\)の組\(G=(V,E)\)である：

• \(E\)の要素は全て、\(V\)の異なる2つの要素からなる集合である。すなわち、

  \(\forall e\in E.\exists v,w\in V.(v\neq w)\land(e=\{v,w\})\)

グラフ\(G=(V,E)\)に対して、\(V\)の要素を\(G\)の頂点、\(E\)の要素を\(G\)の辺という。

グラフは、頂点とそれらの間を結ぶ辺によって図示することができる。今、任意の2つの頂点\(v,w\)に対して その間を結ぶ辺は高々1つしかない (\(\{v,w\}\in E\)であるかそうでないかしか可能性がないため)。 また、辺\(e\in E\)は異なる2つの頂点\(v,w\)と必ず対応するように定義したため、両端が同じ頂点である「ループ」のような辺も存在しない。詳細はグラフ理論 (Wikipedia)やグラフ理論の教科書を参照。

ヒドラゲームには有限根付き木という特別なグラフを用いる。すなわち、

有限

\(V,E\)はいずれも有限集合である。

木

任意の2つの頂点が、ただ1つの道で繋がっている。つまり、任意の\(v,w\in V\ (v\neq w)\)に対してある\(v_0,\dots,v_n\)と\(e_1,\dots,e_n\)が存在して\(e_i=\{v_{i-1},v_i\},v_0=v,v_n=w\)が成り立ち、そのような\(v_i,e_i\)がただ1つしか存在しないことが成り立つ。

根付き木

木であって、さらに根と呼ばれる特別な頂点\(r\in V\)が指定されている。

が成り立つグラフを用いる。定義から、有限根付き木は頂点の集合、辺の集合、根の組\(T=(V,E,r)\)によって表される。 ヒドラゲームにおいて有限根付き木を図示する際は、根は他の頂点よりも下側に置かれ、枝分かれしながら上部に辺が伸びるように描かれる。この姿をヒュドラーに見立てて、ヒドラゲームでは有限根付き木をヒドラと呼ぶ。

木において、辺が1つしか接続していない頂点を葉と呼ぶ。根でない葉をヒドラの頭、あるいはトップノード (top node)、頭とそこに接続した辺を合わせてヒドラの首 (head)と呼ぶことにする。また、首が接続している頂点をその首の根本と呼ぶことにする。 あるヒドラの首が根から直接生えていないならば、首の根本からさらに根の方へ向かう辺がただ1つ存在している。そこでこれを親首と呼ぶことにする。

ルール

ヒドラ\(T=(V,E,r)\)に対してゲームは次のようにプレイされる。ただし\(n\)は現在のターン数であり、1から始まって、以下の行動を繰り返すたびに1ずつ増えていく。

1. ヒドラの首をどれか1つ選び、切り落とす (グラフから除去する)。
2. その後、次の2つの規則に従ってヒドラの首が増える：
   1. もし首が根から直接生えていたら、何も起こらない。
   2. そうでないならば、切った首の親首から先 (親首とは別に切った首の根本に繋がっている辺と頂点すべて) のコピーが、親首の根本から\(n\)本新たに生える。

これを繰り返して、全てのヒドラの首を切り落とし、根だけとすることができたらヘラクレス (つまりプレーヤー) の勝利となる。

テキストによる表現

テキストによるヒドラの表現として、括弧を用いたものがある。

有限の丸括弧の文字列で開閉が正しく対応しているもの、例えば(()(()(())((()))))のようなものをヒドラとみなす。 このとき、ヒドラゲームの手順は以下のようになる：

1. 空の括弧の組()を1つ選ぶ。
2. 選んだ括弧が他の括弧の内側にあるかどうか確認する。
   1. 最も外側にあるならば、単に選んだ()を削除する。
   2. そうでないならば、選んだ()を直接囲む括弧について、その範囲の文字列から選んだ()を除いたうえでコピーして、\(n\)個の複製を直後に追加する。
3. 次のターンに移る。もう一度手順の最初に戻り、\(n\)には1が追加される。

例えば、3ステップ目で(()(()()))を(()(())(())(())(()))に替えられる。

ゲームに勝つ戦略

ヒドラ定理

木での戦略を、ヘラクレスが除去する葉の列とする。もしそれで勝てるなら勝つ戦略、そうでなければ負ける戦略とそれらを呼ぶ。 ターンが経過するごとに増加する首の本数は増えていくため、十分大きなヒドラを討伐することは全く簡単ではなさそうなことが直観的にうかがえる。

ところが実際には、ヘラクレスはいつでもヒドラに勝つことができる。ヒドラゲームを考案したKirbyとParisは、どのような戦略に対してもヘラクレスがヒドラに勝てることを示した。これは (KirbyとParisの) ヒドラ定理と呼ばれ、さらにこの定理はペアノ算術では証明不可能であることが知られている。

より凶悪なヒドラの討伐

KirbyとParisによるヒドラ定理の証明からさらに、ヘラクレスはより“凶悪な”ヒドラの討伐が可能であることがわかる。 いま、ルール2-2においてヒドラの首は\(f(n)\)本増加することにする。ここで関数\(f(n)\)は事前に固定されている (あるいは、現在の状況も鑑みて\(f(n)\)を計算することにしてもよい)。このような状態にあっても、ヘラクレスは戦略にかかわらずヒドラに勝つことができる。

彼らの証明を参考にした定理の証明は次のようになる:

証明:一つ一つの可能木に順序数を割り当てる。() = 0、(H₁H₂...H_n) = \(\omega^{H_1} + \omega^{H_2} + \ldots + \omega^{H_n}\), \(H_1 \geq H_2 \geq \ldots \geq H_n\)(これはノードの次数を無視しているが、次数はヒドラ理論に関係しない)これで\(n\)の値をどう取ろうとヒドラ\(H\)を減少させることが出来ることが証明される。

• もし選んだ葉が根の子だったら、 \(H - 1\)となり、\(H\)未満である。
• もし選んだ葉が \(J = \omega^K\)の子であれば、\(n\omega^{K - 1}\)へ切り落とし、これは有限の\(n\)mに対し\(J\)未満である。

ヒドラの値は必ず減少するためいつかは0となる。

この戦略はFriedmansqueな一人ゲームブーフホルツのヒドラの停止性を計算するのに使える。またグッドスタイン数列にも応用できる。

無限のバリアント

証明より、無限のヒドラは負けの戦略のみがあるように思われる。例えば、\(\aleph_0\)の葉を持つ根は絶対にに倒されない。\(\aleph_0 - 1 = \aleph_0\)かつ、木は切り落としても全く変わらないからである。また珍しい例として、一つの枝が伸び続ける木がある。そこには葉がないため、プレイヤーは行動が出来ない。それは勝ちなのか負けなのか?

1. プレイヤーは負ける。彼はヒドラを根のみに削減できないためである。
2. プレイヤーは勝つ。ヒドラゲームは一人ミゼールゲームなので、そこに行動が残されていない場合はプレイヤーの勝ちである。

ヒドラ関数

しばしば、ヒドラを倒すためのターン数はとても大きくなる。たくさんのパラメータがありすぎるため、それらを二、三の規則で単純化する。

• それぞれのヒドラは長さ\(k\)のパスと\(k + 1\)の接点の一連を持つ。
• 戦略は、一番右のノードからヒドラの頭を狩るというものである。ここで、丸括弧表記のように、ヒドラのコピーは常に右側に追加されている。\(n\)の値は、1,2,3,...と増加する。

\(\text{Hydra}(k)\)をゲームに勝つための必要なターン数とする。そうすると、

\begin{eqnarray*} \text{Hydra}(0) &=& 0\\ \text{Hydra}(1) &=& 1\\ \text{Hydra}(2) &=& 3\\ \text{Hydra}(3) &=& 37\\ \text{Hydra}(4) &>& f_{\omega*2 +4}(5) \approx \{5,5,4,3\} >> \text{グラハム数}\\ \text{Hydra}(5) &>& f_{\omega^{\omega*2 + 4}}(5) \approx \{5,5 (1) (1) 5,5,5,5,5\}\\ \end{eqnarray*}

となる。\(\text{Hydra}(k)\)の成長率はε₀ほどである。これは驚くことではない。なぜなら\(\varepsilon_0\)はペアノ算術の証明論的順序数だからである。これにより、ヒドラ関数はグッドスタイン数列やBEAFのテトレーション配列程となる。

外部リンク

• Bauer, Andrej. The hydra game. 
• David Madore, "Hercules and the hydra".

出典

• Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic", Bulletin of the London Mathematical Society 14: 285–293.
• Weisstein, Eric W., "Goodstein Sequence", MathWorld.
• Some elements of a proof that Goodstein's theorem is not a theorem of PA, from an undergraduate thesis by Justin T Miller
• A Classification of non stanard models of Peano Arithmetic by Goodstein's theorem - Thesis by Dan Kaplan, Franklan and Marshall College Library
• Definitions of Goodstein sequences in the programming languages Ruby and Haskell, as well as a large-scale plot
• Goodstein Sequences: The Power of a Detour via Infinity - good exposition with illustrations of Goodstein Sequences and the hydra game.

参考：巨大数論