ブッフホルツヒドラ

数学、特に数理論理学、グラフ理論、数論において、ブッフホルツのヒドラゲームは、数学的な木からピースを切り落とすというアイデアに基づいたシングルプレイヤーゲームであるヒドラゲームの一種です。ヒドラゲームは、急速に増加する関数 を生成するために使用でき、これは最終的に「」で証明可能に完全であるすべての再帰関数を支配し、すべてのヒドラゲームの停止は で証明可能に完全ではありません。^[1]${\displaystyle BH(n)}$${\displaystyle {\textrm {ID}}_{\nu }}$${\displaystyle {\textrm {(}}\Pi _{1}^{1}{\textrm {-CA)+BI}}}$

ゲームは、次の特性を持つ 有限のルート付き連結木であるヒドラ上でプレイされます。 ${\displaystyle A}$

• のルートには特別なラベルがあり、通常は と表記されます。${\displaystyle A}$${\displaystyle +}$
• の他のノードにはラベル が付きます。${\displaystyle A}$${\displaystyle \nu \leq \omega }$
• のルートの直上にあるすべてのノードにはラベルが付きます。${\displaystyle A}$${\displaystyle 0}$

プレイヤーがのトップノードを削除すると、ヒドラは任意の（ は現在のターン数）を選択し、次のように新しいヒドラに変身します。が の親を表し、 がを削除した後に残るヒドラの部分を表すものとします。 の定義はのラベルによって異なります。 ${\displaystyle \sigma }$${\displaystyle A}$${\displaystyle n\in \mathbb {N} }$${\displaystyle n}$${\displaystyle A(\sigma ,n)}$${\displaystyle \tau }$${\displaystyle \sigma }$${\displaystyle A^{-}}$${\displaystyle \sigma }$${\displaystyle A(\sigma ,n)}$${\displaystyle \sigma }$

• のラベルが0 での根である場合、=となります。${\displaystyle \sigma }$${\displaystyle \tau }$${\displaystyle A}$${\displaystyle A(\sigma ,n)}$${\displaystyle A^{-}}$
• のラベルが0 であるが のルートではない場合は、とそのすべての子のコピーが作成され、それらとの親の間にエッジが追加されます。この新しいツリーは です。${\displaystyle \sigma }$${\displaystyle \tau }$${\displaystyle A}$${\displaystyle n}$${\displaystyle \tau }$${\displaystyle \tau }$${\displaystyle A(\sigma ,n)}$
• のラベルが何らかの に対して である場合、はラベル を持つ最初のノードの下側にあるとします。を から始めてのラベルを と 0 に置き換えることによって得られるサブツリーとして定義します。 を取って に置き換えるとが得られます。この場合、 の値は重要ではありません。${\displaystyle \sigma }$${\displaystyle u}$${\displaystyle u\in \mathbb {N} }$${\displaystyle \varepsilon }$${\displaystyle \sigma }$${\displaystyle v<u}$${\displaystyle B}$${\displaystyle A_{\varepsilon }}$${\displaystyle \varepsilon }$${\displaystyle u-1}$${\displaystyle \sigma }$${\displaystyle A(\sigma ,n)}$${\displaystyle A}$${\displaystyle \sigma }$${\displaystyle B}$${\displaystyle n}$
• のラベルが の場合、のラベルを に置き換えることによって が得られます。${\displaystyle \sigma }$${\displaystyle \omega }$${\displaystyle A(\sigma ,n)}$${\displaystyle \sigma }$${\displaystyle n+1}$

が の右端のヘッドである場合、と書きます。一連の動きは戦略と呼ばれます。戦略は、有限回数の動きの後にヒドラが根に減少する場合、勝利戦略と呼ばれます。ヒドラが非常に大きく成長したとしても、これは常に終了します。^[1]${\displaystyle \sigma }$${\displaystyle A}$${\displaystyle A(n)}$

1987 年のブッフホルツの論文では、ヒドラと無限整基礎木 (または ブッフホルツ関数に関連付けられた表記法の対応する項。これは必ずしも順序表記法 には属さない) との間の標準的な対応が、右端の葉を選択する基本的なシーケンスと 無限整基礎木に対する操作または の対応する項に対する操作を保存することが示されました。^[1]${\displaystyle T}$${\displaystyle OT\subset T}$${\displaystyle (n)}$${\displaystyle [n]}$${\displaystyle T}$

ブッフホルツのヒドラのヒドラ定理は、いかなるヒドラにも負ける戦略は存在しないと述べているが、これは証明不可能である。^[2]${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$

 木が というラベルの付いたノードを持つ 1 つの枝だけから構成されているとします。そのような木を と呼びます。 すべての に対して、 が勝利戦略となる ようなものが存在することは、 では証明できません 。(後者の表現は、木 を取り、それを、次に、次になどを使用して まで変換することを意味します。) ^[2]${\displaystyle x}$${\displaystyle +,0,\omega ,...,\omega }$${\displaystyle R^{n}}$${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$${\displaystyle x}$${\displaystyle k}$${\displaystyle R_{x}(1)(2)(3)...(k)}$${\displaystyle R_{x}}$${\displaystyle n=1}$${\displaystyle n=2}$${\displaystyle n=3}$${\displaystyle n=k}$

 を、上で定義したように勝利戦略となる 最小の として定義します 。ヒドラ定理により、この関数は明確に定義されますが、 ではその全体性が証明できません。ヒドラは非常に速く成長します。これは、殺すために必要なターン数がグラハム数よりも大きく、カービー-パリスヒドラを殺すのに必要なターン数よりも大きいためです。 には、カービー-パリスヒドラ全体が枝として存在します。正確には、その成長率は、 証明のない基本シーケンスの未指定システムに関して に匹敵すると考えられています。ここで、 は ブッフホルツ関数を表し、は の強さを測定するTakeuti-Feferman-Buchholz 順序数です。 ${\displaystyle BH(x)}$${\displaystyle k}$${\displaystyle R_{x}(1)(2)(3)...(k)}$${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$${\displaystyle R_{x}(1)(2)}$${\displaystyle R_{x}(1)(2)(3)(4)(5)(6)}$${\displaystyle f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(x)}$${\displaystyle \psi _{0}}$${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$

BH 関数の最初の 2 つの値は実質的に退化しています: および。弱い木関数と同様に、 は非常に大きいですが、それほどではありません。^{[引用が必要]}${\displaystyle BH(1)=0}$${\displaystyle BH(2)=1}$${\displaystyle BH(3)}$

ブッフホルツのヒドラは最終的にはTREE(n)とSCG(n)を上回りますが^[要出典]、ローダーや有限約束ゲームの数値よりも弱い可能性があります。

いくつかのヒドラと序数の間には 1 対 1 の対応関係を作ることができます。ツリーまたはサブツリーを序数に変換するには、次のようにします。

• ノードの直下の子すべてを順序数に帰納的に変換します。
• それらの子の順序数を合計します。子がいない場合は、0 になります。
• ノードのラベルが + でない場合は を適用します。ここで はノードのラベル、 はブッフホルツ関数です。${\displaystyle \psi _{\alpha }}$${\displaystyle \alpha }$${\displaystyle \psi }$

結果の順序式は、正規形である場合にのみ役立ちます。次に例をいくつか示します。

• 「ヒドラス」、アグニヨの数学の宝箱、 2021-09-04取得

 この記事には、CC BY-SA 3.0 ライセンスに基づいて利用可能なテキストが組み込まれています。