| TREE数列 | |
|---|---|
| 型 | 組合せ数学 |
| 急増加関数 | ≥\(f_{\vartheta(\Omega^{\omega}\omega)}(n)\) |
TREE数列とは、グラフ理論に起因するとても成長の早い関数である。数理論理学者の Harvey Friedman によって考案された。[1][2]
定義[]
次の特徴を持つ根付きの k-ラベル付き木 の列 T1, T2 ... があるとする。
- それぞれのグラフTiは最大でiの頂点を持つ。
- 列の中には、列の前にあるグラフがそれよりも後ろの方にあるグラフに inf保存かつラベル保存埋め込み可能 であるようなペアは１つもない。
WQO理論とクラスカルの木の定理によると、そのような列は無限列にはなりえない[3]。Harvey Friedman はこの問いを拡張した、 与えられたkに対して、列の最大長はなんだろう？
この最大長は、kの関数として TREE[k] とあらわされる。 最初の二つの値は TREE[1]=1、そしてTREE[2]=3である。次の数TREE[3]は有名で、とても大きい。TREE[3] > nX(5) はすべての「十分な量の」Xで証明されている。[4]
TREE[n]は後述するtree(n)より早く成長し、かつtree(n)は適切な基本列系に関する急増加関数で\(f_{\textrm{SVO}}(n)\)と近似される関数よりも早く成長する。ここで\(\textrm{SVO}\)は小ヴェブレン順序数である。詳しくは[[#\(\text{tree}(n)\) の値]]を参照。TREE数列はヒドラゲームやグッドスタイン数列よりも強いが、サブキュービックグラフ数やブーフホルツのヒドラよりも弱いと信じられている。
Chris Birdは バードの配列表記を使って\(\text{TREE}[3] > \lbrace3, 6, 3 [1 [1 \neg 1,2] 2] 2\rbrace\)、と主張した。[5]
弱いtree関数[]
tree(n)、弱いtree関数 を次のような1-labelled trees の列の最大長と定義する。
- 全てのグラフはすべての場所kでk+n以下の頂点を持つ。
- 列の中には列の前にあるグラフがそれよりも後ろの方にあるグラフに位相同型的埋め込み可能であるペアは１つもない。
Adam P. Goucher はこの関数についての情報を発見したとGoogology Wikiに書かれていたが、実際にはそれに関する証明は一切なかった。
- tree(n)は急増加関数で\(\textrm{SVO}\) の成長レベルを持つ。
- TREE[3] > treetreetreetreetree8(7)(7)(7)(7)(7)。
英語版の記事およびAdam P. Goucher本人はこれらの未証明な結果が証明つきの結果であるように誤って描写していた過去があり、それに伴ってかいくつかのwebページや解説動画でも同様の記述が現れることがあるが、ソースが存在しない場合は注意が必要である。
より大きい下限も見つかっているとされている。 \(\text{tree}_2(n)=\text{tree}^n(n)\) かつ \(\text{tree}_3(n)=\text{tree}_2^n(n)\) としたときに、 \(\text{TREE}[3] > \text{tree}_3(\text{tree}_2(\text{tree}(8)))\) が成立する。これは、 \(n = \text{tree}^{\text{tree}(8)}(\text{tree}(8))\) としたときの、treetreetree...tree(n)...(n)(n)(n) (n段重ね)とも表せる。[6]
Googology Wikiに記載されていたTREEやtreeの評価はほぼ全て証明がないため、信憑性については疑問である。
\(\text{tree}(n)\) の値[]
\(\text{tree}(1) = 2, \text{tree}(2) = 5\) そして \(\text{tree}(3) \geq 2^{18}-4\) となる。 \(\text{tree}(1)\) は次の列が解である:
(()) ()
\(\text{tree}(2)\) 少し大きいが, 二つの最長列が存在する。
((())) (()()()) (()()) (()) ()
もしくは:
(()()) (((()))) ((())) (()) ()
\(\text{tree}(3)\) の値を決定するのは難しいが、その解の長さを持ったたくさんの最長列が存在する。
\(\mathrm{tree}(n)\)の値は数理論理学者の木原貴行によって以下のように評価された[7]． \begin{eqnarray*} \mathrm{tree}(1.00001n+2)>f_{\textrm{SVO}}(n) \end{eqnarray*}
説明[]
以下の説明はソースがないため要検証である。
グラフをそのまま書かずに可視化するのは難しいため、もっとコンパクトにグラフを表現する必要がある。(), [], {} と多くの種類のかっこで書かれた言語を考える。かっこたちはペアになっていて、互いにネストを形成できる。例えば、次のようなものがこの言語では「正しい」と言える。
[]
([])
{[()]()}
[(){[[]]}(){(())[]}]
文字列Aがあるとする。対応するかっこのペアをノードと呼ぶことにする。子を、元のノードに1階層奥にネストされたノードであると定義する。例えば、Aを {[()()][][()]} であるとすると、{}の子は[]であり、()ではない。
ノードの持つ子が2つ未満ならば、それを削除可能と呼ぶ。例えば、Aを {[()()][][()]} であるとすると、全ての()、 最後の2つの[]は削除可能であるが、最初の[]と{}はそうでない。
もし文字列 A から文字列Bに、削除可能なノードを削除することで変換することが出来るならば、AはBへ縮約可能であるという。BであらわされるグラフがAであらわされるグラフと位相同型的埋め込み可能であることと文字列Aが文字列Bへ縮約可能であることは同値である。
これらすべてを考え、TREE[k]と同じであることが期待されるものを定義できる。次のような文字列列があるとする、
- k種類以下のブラケットを使っている
- 第1の文字列は最大1個の括弧のペア、2つ目は2個のペア…となっている。
- どの文字列も、その文字列から前の文字列に縮約可能でない。
TREE[K]はこのような列の最大長である。
k=1, 文字列列は1つのみ、(). k=2なら、 文字列列は、 (),[[]],[] となる。
弱いtree関数[]
上記と同様に定義すると:
()以外に括弧を使ってはならない。- 始めの文字列は最大1 + k個の括弧のペア、2番目は 2 + k 個の括弧のペア…となっている。
- どの文字列も後の文字列から carvable ではない。
tree(K)はこのような列の最大長である。
動画[]
様々な解説動画が存在するが、証明や出典の明記されていない記述については注意が必要である。
出典[]
- ↑ H. Friedman, [FOM] 273:Sigma01/optimal/size
- ↑ H. Friedman, [FOM] n(3) < Graham's number < n(4) < TREE[3]
- ↑ 木原貴行, 巨大数の樹海へようこそ！
- ↑ How large is TREE(3)
- ↑ Chris Bird, Beyond Bird's Nested Arrays II, page 10
- ↑ How does TREE(3) grow to get so big? Need laymen explanation
- ↑ 木原貴行，とりマセΣ^0_2，Lower bounds for tree(4) and tree(5)，