FANDOM


Hydra3.svg

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

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

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

ルール 編集

次のようにプレイされる:

  • 有限根付き木\(T\)を取る。その根を\(r\)とする。
  • 木から葉頂点と自然数\(n\)を取る。その葉を\(a\)、その親を\(b\)とし:
    1. \(a\)をTから削除する
    2. もし\(b = r\)なら、何も変わらない。それ以外は、\(c\)を\(b\)の親とし\(b\)からなる部分木とその全ての子を考える; それを\(n\)回繰り返し、それを\(c\)に取り付ける。

これと同様のことを文字列と丸括弧を使い表現できる。

  • 有限の丸括弧の文字列、例えば(()(()(())((()))))を取る。
  • 空の()の組と\(n\)を取る。
    1. それを削除する。
    2. もしその親が最も外側でなければ、親に\(n\)個のコピーを追加する。

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

プレイヤーは葉と自然数を選び続けてヒドラの頭を刈り続ける。もしそれが根のノードのみになればプレイヤーの勝ちである。

ヒドラ理論 編集

木での戦略を、葉と自然数の列とする。もしそれで勝てるなら勝つ戦略、そうでなければ負ける戦略とそれらを呼ぶ。

いくらかの戦略は明らかに勝つ戦略である。繰り返し\(n = 0\)を選べば、ヒドラは必ず増加しないため、簡単に勝てる。だが多くの戦略(特に大きな\(n\))はヒドラはとても速く成長し、それで問いが立ち上がる:プレイヤーはヒドラを増殖させ続けることによって負けるのか?KirbyとParisはこの問いに"No"と答えた。プレイヤーには勝つ戦略しかなくて、負けるものは一つもないとした。これはヒドラ理論と呼ばれ、これはペアノ公理では証明不可能である。定理の彼らの証明は次のようになる:

証明:一つ一つの可能木に順序数を割り当てる。() = 0、(H1H2...Hn) = \(\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


参考:巨大数論

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki