ヒドラゲームと巨大数論

皆さまこんにちは.CDSLの河竹純一です.

今回は巨大数という概念について紹介させていただきます.

みなさんは「巨大数」と聞いてどれぐらいの数字を想像するでしょうか.おそらく,億,兆,京,垓,~無量大数といった単位,世界的企業Googleの語源となった「グーゴル(10の100乗)」,あるいはスーパーコンピュータの処理能力は地球上の人間が計算して何年かかるだとか,宇宙の広さといった概念的なものを想像するかもしれません.

その中でも日常的に扱う数字は精々数万~数億まででしょうから,これらは確かに私たちにとってはるかに大きい「巨大な数」ではありますが,あくまでこれらは十進数としてそのまま表記することが可能な数,あるいは容易に指数であらわすことができるものにとどまっています.一方「巨大数論」における巨大数は,どこからどこまでを巨大数とするかが曖昧なものになっているとはいえ,少なくとも上記のような数を主題とすることはほとんど無いといっても過言ではないでしょう.

さて,それでは巨大数論ではどのような数を扱うのかと気になる方もいるかもしませんが,それを説明するには巨大数にどのようなものがあるのかを順に見ていく他ありません.というのも,上記のようにその範囲が曖昧であり,巨大数の多くが巨大数論という枠でしか価値のない創作された数,ただ巨大にすることを目的とした数であることに起因しています.したがって,巨大数論は少数のアマチュア愛好家によって開拓された学問であり,体系的にまとめられたのもここ数十年のことです.こと日本においてはインターネット掲示板2ちゃんねるで活発に議論されたことや小林銅蟲氏によって漫画化(小林銅蟲(2017)『寿司 虚空編』三才ブックス)されたこともあり,一種のサブカルチャーとしての側面も持ち合わせているといえます.

閑話休題,普通は巨大数の入門といえばロバート・ムナフォの数のクラス分けや数学の証明に使われた最大の数としてギネスブックに載っているグラハム数あたりから始めるのかもしれませんが,今回は少し変わった話題を紹介してみようと思います.

図1 ヒドラのイメージ

さて,題名にもある「ヒドラゲーム」ですが,おそらく多くの方は「ヒドラ」を知っているかと思います.ヒドラは上の図のような首が複数ある怪物で,ギリシャ神話に出てきます.この「ヒドラゲーム」ですが,ゲームとは名ばかりで,Kirbyらのグッドスタインの定理に関する消極的事実を証明する論文(Kirby, L. and Paris, J. (1982) Accessible independence results for Peano arithmetic. Bulletin London Mathematical Society14(4): 285–293.doi:10.1112/blms/14.4.285)の中で出てくる,あるルールに基ずくターン制のシミュレーションとなっています.そのルールは以下のようなものです.

ルール
・プレイヤーは1ターンに一度,ヒドラの首を一本切ることができる.
・ヒドラは1ターンに一度,以下の法則で首を増殖させる.
・プレイヤーはヒドラのすべての首を切ったら勝利する.

法則
・ヒドラは有限の木構造を持っており,ヒドラの首をセグメント,ヒドラの首の根本(分岐点)をノード,すべてのノードの原点をルートとする.
・ヒドラは,前のターンでプレイヤーに切られたセグメントの一つ下のセグメント(ルートに近いセグメント)から上に伸びている木の形をコピーする
・そこからさらにひとつ下のノードから,コピーした木を生やす
・生やす数は,ヒドラのターンで数えてnターン目にn本となる
・切られたセグメントから二つ下のノードが存在しない場合,ヒドラの首は生えない

以下に,例として簡単なヒドラの図と1ターン目のそれぞれの動きを示します.

図2 プレイヤーのターン

プレイヤーは任意のヒドラの首(セグメント)を一本切ることができます.ここでは例として赤色のセグメントを切断します.

図3 ヒドラのターン

ヒドラは切断されると前のターンでプレイヤーに切られたセグメントの一つ下のセグメントから上に伸びている木の形をコピーし,さらにひとつ下のノードから,1ターン目なので一本コピーした木を生やします.

以上のような行動を繰り返し,ヒドラのすべてのセグメントがなくなればプレイヤーは勝利します.

実はプレイヤーが勝利することは非常に簡単であり,ヒドラのルートから伸びているセグメントを切ることによってヒドラは新たな首を生やすことが出来ないため,勝とうと思えばどんなヒドラであっても勝てるということは容易に想像することができます.

ヒドラゲームの面白い点は,どのようなヒドラであっても,どのような手順でプレイヤーがヒドラの首を切っても必ずプレイヤーが勝つ点にあります.つまり,おおよそプレイヤーが取り得る「最悪手」を毎ターン選択したとしても勝つことができるのです.(順序数を使うとなぜ勝てるのかがわかるがここでは割愛する)これは,一見するとヒドラの生やす首の本数が毎ターン増えることに矛盾するように思えます.

ここで,ヒドラのすべての首を切るのにかかるターン数を関数にすることを考えてみます.想定するヒドラをnのセグメント,n+1のノードを持つ直線的なものとすると,ターン数H(n)(HはHydraの頭文字)は以下のようになることが知られています.

H(1) = 1
H(2) = 3
H(3) = 37
H(4) > F[ω*2+4](5) ≈ {5, 5, 4, 3} (>>> グラハム数)

F[α](n)は急増加関数,{5, 5, 4, 3}のような{}で囲まれた表記は配列表記と呼ばれるものであり,いずれにしても気が遠くなるような概念です.(グラハム数は比較的その大きさがわかりやすいので調べてみると良い)このように,n ≥4でH(n)は爆発的な増加をするということが知られています.

巨大数を作ることは,すなわち”強い”関数を作ることであり,その関数を比べることによって数の大きさを比較することが可能となっています.(そうすることでしか比較することができないほど大きい)そしてそれらの関数はいくつかの定義と法則で表すことができ,プログラミング的な思考によって生み出されているといえます.したがって,巨大数論はコンピュータの発展とともに急速に理解が深まった学問であるともいえます.

今回はあくまで巨大数という世界があることについての紹介でしたが,また機会があればハイパー演算子等の基礎的なところから巨大数の世界を解説しようと思います.

参考
フィッシュ(2017)『巨大数論 第二版』株式会社インプレスR&D

Leave a Reply