ヒドラゲーム

数学、特にグラフ理論と数論において、ハイドラゲームは、ハイドラと呼ばれる数学的な木上でプレイされるシングルプレイヤーの反復的な数学ゲームであり、通常、ハイドラが拡大すると同時にハイドラの「頭」を切り落とすことが目的です。ハイドラゲームは、大きな数や無限序数を生成したり、特定の数学理論の強さを証明したりするために使用できます。^[1]

TREEやSCGなどの組み合わせ関数とは異なり、これらの急速に増加する関数値を計算するために検索は必要ありません。ゲームが停止するまで、変換ルールをツリーに適用し続けるだけです。

単純なヒドラゲームは次のように定義できます。

• ヒドラは有限のルート付きツリーで、サイクルのない接続されたグラフであり、特定のノードがツリーのルートとして指定されます。ルート付きツリーでは、各ノードには 1 つの親 (親のないルートを除く) と一連の子があります。一方、ルートなしツリーでは親子関係がなく、ノード間のエッジのみを参照します。${\displaystyle R}$
• プレイヤーは各ターンにツリーからリーフ ノードと自然数を選択します。リーフ ノードは、子を持たないノード、または ではない次数 1 のノードとして定義できます。${\displaystyle x}$${\displaystyle n}$${\displaystyle R}$
• リーフ ノード を削除します。を の親とします。 の場合は、ステージ 2 に戻ります。 でない場合は、を の親とします。次に、後順トラバーサル中に の既存の子の後に表示されるように、リーフ ノードを の子として作成します(視覚的には、これらの新しいノードは既存の子の右側に表示されます)。次に、ステージ 2 に戻ります。${\displaystyle x}$${\displaystyle a}$${\displaystyle x}$${\displaystyle a=R}$${\displaystyle a\neq R}$${\displaystyle b}$${\displaystyle a}$${\displaystyle n}$${\displaystyle b}$${\displaystyle b}$

ヒドラは各ターンで無制限の数の葉を増やすかもしれませんが、ゲームは最終的に有限回のステップで終了します。 がルートと葉の最大距離で、この距離にある葉の数である場合、 に対する帰納法を使用して、プレーヤーが常にヒドラを殺すことを証明できます。 の場合、葉を取り除いてもヒドラが成長することはないため、ターン後にプレーヤーが勝ちます。 一般に の場合、ルートから未満の距離にある葉を伴う動きと、ちょうど の距離にある葉を伴う動きの 2 種類の動きを検討します。 最初の種類の動きは深さ のゲームの動きと同じでもあるため、帰納法の仮説により、そのような動きを有限回行った後、プレーヤーは深さ にある葉を選択する以外に選択肢がないことがわかります。 この深さに新しいノードを導入する動きはないため、このプロセス全体を繰り返すことができるのは までであり、その後は深さ に葉がなくなり、ゲームの深さは (最大で) になります。帰納仮説を再度適用すると、プレイヤーは最終的に全体的に勝利しなければならないことがわかります。 ${\displaystyle n}$${\displaystyle d}$${\displaystyle w}$${\displaystyle d}$${\displaystyle d=1}$${\displaystyle w}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d-1}$${\displaystyle d}$${\displaystyle w}$${\displaystyle d}$${\displaystyle d-1}$

これは、プレイヤーが最終的には勝つことを示していますが、非常に長い時間がかかる可能性があります。例として、次のアルゴリズムを考えてみましょう。一番右の葉（つまり、ルートに最も近いレベルにある最も新しい葉）を選択し、 を1 回目、2 回目、などと設定し、常に1 ずつ増加させます。ヒドラが 1 つの長さの枝を持つ場合、 の場合、ヒドラは 1 ステップで殺されますが、 の場合は 3 ステップで殺されます。 には 11 ステップが必要です。 には 1114111 ステップが必要です。^{[2] は}正確に計算されています。^[3]と をn回ネストします。 ${\displaystyle n=1}$${\displaystyle 2}$${\displaystyle n}$${\displaystyle y}$${\displaystyle y=1}$${\displaystyle y=2}$${\displaystyle y=3}$${\displaystyle y=4}$ ${\displaystyle y=5}$${\displaystyle F(x)=2^{x}\cdot (x+2)-1}$${\displaystyle F^{n}(x)}$${\displaystyle F}$${\displaystyle HYDRA(5)=2\cdot F^{F^{2}(3)+1}(F^{2}(3)+1)+1=2\cdot F^{22539988369408}(22539988369408)+1}$

ヒドラゲームの一般的な解は次の通りである: ^[4]

ルートに近いヘッドがすべて特異である（それ以上の「右」の枝がない）場合に、深さ n のヘッドを減分するために必要なステップ数を表します 。${\displaystyle F_{i}(x)}$

それからそして。 ${\displaystyle F_{i+1}(x)=F_{i}^{x}(x+1)}$${\displaystyle F_{1}(x)=2\cdot (x+1)-1=2x+1}$

答えは次のとおりです。 ${\displaystyle hydra(n)}$${\displaystyle F_{1}(F_{2}(F_{3}(\ldots F_{n-1}(F_{n}(1))\ldots )))}$

この関数の成長率は標準の急成長階層よりも速く、だけが急成長階層の速度で成長し、解は の n 番目のネストになります。 ${\displaystyle F_{i}(x)}$${\displaystyle F_{i}(x)}$

カービー・パリス・ヒドラは、上で定義したヒドラの 4 番目のルールを変更することによって定義されます。

4 _KP :がの親であると仮定します。をルートとするサブツリーのコピーを に接続されている他のすべてのノードの右側に接続します。ステージ2に戻ります。^[5]${\displaystyle b}$${\displaystyle a}$${\displaystyle a\neq R}$${\displaystyle n}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$

このルールは、新しい葉だけを追加するのではなく、サブツリー全体の複製を追加します。他のすべてを同じにしておくと、今度はターンが必要になり、のステップ が必要になり、 のステップが必要になり、グラハムの数よりも多くのステップが必要になります。この関数の成長率は と同等で、急成長階層では に等しくなります。${\displaystyle y=1}$${\displaystyle 1}$${\displaystyle y=2}$${\displaystyle 3}$${\displaystyle y=3}$${\displaystyle 37}$${\displaystyle y=4}$${\displaystyle f_{\varepsilon _{0}}(n)}$

これは最も強力なヒドラではありません。ブッフホルツのヒドラの方が強力なヒドラです。^[6]これはラベル付きの木を伴います。ルートには一意のラベル（ と呼びます）があり、他の各ノードには負でない整数または のラベルがあります。^[7]${\displaystyle R}$${\displaystyle \omega }$

1. ヒドラは有限の根を持つラベル付きの木です。根には というラベルを付けます。根に隣接するすべてのノード(根が常に終了していることを保証するために重要) と、他のすべてのノードに負でない整数または というラベルを付けます。${\displaystyle R}$${\displaystyle 0}$${\displaystyle \omega }$
2. 各ステージでリーフノードと自然数を選択します。${\displaystyle x}$${\displaystyle n}$
3. 葉 を削除します。を の親にします。 の場合は何も起こりません。ステージ 2 に戻ります。${\displaystyle x}$${\displaystyle a}$${\displaystyle x}$${\displaystyle a=R}$
4. のラベルが の場合、は の親であると想定します。に接続されている他のすべてのノードの右側に、をルートとするサブツリーのコピーを接続します。ステージ 2 に戻ります。${\displaystyle x}$${\displaystyle 0}$${\displaystyle b}$${\displaystyle a}$${\displaystyle n}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$
5. x のラベルが の場合、それを に置き換えます。ステージ 2 に戻ります。${\displaystyle \omega }$${\displaystyle n+1}$
6. のラベルが正の整数 の場合、ツリーを下ってラベル のノードを探します。ルートに隣接するすべてのノードに のラベルが付いているため、このようなノードは存在します。ルート を持つサブツリーのコピーを取得します。このサブツリーで置き換えます。ただし、(サブツリーのコピーのルート) を で再ラベルします。コピーされたサブツリーで と同等の を呼び出し( はに、はに)、 0 で再ラベルします。ステージ 2 に戻ります。^[8]${\displaystyle x}$${\displaystyle u}$${\displaystyle c}$${\displaystyle <u}$${\displaystyle 0}$${\displaystyle c}$${\displaystyle x}$${\displaystyle x}$${\displaystyle u-1}$${\displaystyle x}$${\displaystyle x'}$${\displaystyle x}$${\displaystyle x'}$${\displaystyle c}$${\displaystyle x}$${\displaystyle (x')}$

驚くべきことに、ヒドラはものすごく大きく成長することができるにもかかわらず、このシーケンスは常に終了します。^[9]

カービー・パリス・ヒドラのルールは簡単です。ヒドラは順序もラベルも付いていないルート付き木 から始めます。各ステージで、プレーヤーは切り落とす葉ノードと負でない整数を選びます。 がルート の子である場合、 は木から削除され、そのターンは何も起こりません。そうでない場合は、を の親 にし、を の親 にします。 を木から削除し、 変更された のコピーを の子として に追加します。ヒドラが 1 つのノードに減るとゲームは終了します。 ${\displaystyle T}$${\displaystyle c}$${\displaystyle n}$${\displaystyle c}$${\displaystyle r}$${\displaystyle p}$${\displaystyle c}$${\displaystyle g}$${\displaystyle p}$${\displaystyle c}$${\displaystyle n}$${\displaystyle p}$${\displaystyle g}$

増加の速い関数を得るには、最初のステップで を固定し、次に、 などとし、どこでカットするかについての簡単なルール、たとえば常に右端の葉を選ぶことを決めます。すると、 は、 長さ のパス、つまりノードの線形スタック から始めてゲームを終了するために必要なステップ数です。は最終的に、ペアノ算術で証明可能全であるすべての再帰関数を支配し、 で証明可能全になります。^[10]${\displaystyle n}$${\displaystyle n=1}$${\displaystyle n=2}$${\displaystyle n=3}$${\displaystyle \operatorname {Hydra} (k)}$${\displaystyle k}$${\displaystyle k+1}$${\displaystyle \operatorname {Hydra} (k)}$${\displaystyle \mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})}$

これは、括弧の文字列を使用して表現することもできます。

• のような括弧の有限シーケンスから始めます。${\displaystyle (()(()(())((()))))}$
• 空のペアと負でない整数を選択します。${\displaystyle ()}$${\displaystyle n}$
• ペアを削除し、その親が最も外側のペアでない場合は、その親を取得して そのコピーを追加します。${\displaystyle n}$

たとえば、 の場合、となります。次は の値のリストです。 ${\displaystyle n=3}$${\displaystyle (()(()\mathbf {()} ))\implies (()(())(())(())(()))}$${\displaystyle \operatorname {Hydra} (k)}$

• ${\displaystyle \operatorname {Hydra} (0)=0}$
• ${\displaystyle \operatorname {Hydra} (1)=1}$
• ${\displaystyle \operatorname {Hydra} (2)=3}$
• ${\displaystyle \operatorname {Hydra} (3)=37}$
• ${\displaystyle \operatorname {Hydra} (4)>f_{\omega \cdot 2+4}(5)\gg {\text{Graham's number}}}$
• ${\displaystyle \operatorname {Hydra} (5)>f_{\omega ^{2+4}}(5)}$
• ${\displaystyle \operatorname {Hydra} (6)>f_{\underbrace {\omega ^{\cdots ^{\omega }}} _{6}}(5)}$

ブッフホルツのヒドラゲームは、数学論理におけるヒドラゲームであり、数学的な木からピースを切り落とすというアイデアに基づいたシングルプレイヤーゲームです。ヒドラゲームは、急速に増加する関数 を生成するために使用できます。この関数は、最終的にすべての証明可能な完全再帰関数を支配します。これは、カービー-パリのヒドラの拡張です。急速に増加する関数を取得するために使用するものは、カービー-パリのヒドラと同じですが、ブッフホルツのヒドラは幅だけでなく高さも増加するため、の成長率は よりもはるかに高くなります。 ${\displaystyle BH(n)}$${\displaystyle BH(n)}$${\displaystyle f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)}$

• ${\displaystyle BH(1)=0}$
• ${\displaystyle BH(2)=1}$
• ${\displaystyle BH(3)<f_{\varepsilon _{0}}(3)}$

このシステムは、たとえば無限順序数の順序表記を作成するためにも使用できます。 ${\displaystyle \psi _{0}(\Omega _{\omega })=+0(\omega )}$

• グッドスタインの定理

 この記事には、CC BY 4.0 ライセンスの下で利用可能な Komi Amiko によるテキストが組み込まれています。

• ヒドラゲーム
• ヘラクレスとヒドラ
• PBS Infinite Seriesによる数学のヒドラを倒す