Fandom

巨大数研究 Wiki

TREE数列

549このwikiの
ページ数
新しいページをつくる
コメント0 シェアする
TREE数列
組合せ数学
急増加関数 ≥\(f_{\vartheta(\Omega^{\omega}\omega)}(n)\)

TREE数列とは、グラフ理論に起因するとても成長の早い関数である。数理論理学者の Harvey Friedman によって考案された。[1][2]

定義 編集

次の特徴を持つ k-labeled treesの列 T1, T2 ... があるとする。

  1. それぞれのグラフTiは最大でiの頂点を持つ。
  2. 列の中には位相同型的埋め込み可能 である組は1つもない。

Kruskal's tree theoremによると、そのような列は無限列にはなりえない。Harvey Friedman はこの問いを拡張した、 与えられたkに対して、列の最大長はなんだろう?

この最大長は、kの関数、もしくは TREE(K)としてあらわされる。 最初の二つの値は TREE(1)=1、そしてTREE(2)=3である。次の数TREE(3)は有名で、とても大きい。TREE(3) > nX(5) はすべての「十分な量の」Xで証明されている。[3]

TREE(n)は急増加関数で\(f_{\vartheta(\Omega^\omega)}(n)\)よりも早く成長する。これは、巨大数研究者にとっても非常に大きな数で、 \(\vartheta(\Omega^\omega)\) はBEAFでは「線形配列次元の配列」の強さとなる。この数列はヒドラゲームグッドスタイン数列よりも強いが、サブキュービックグラフ数ブーフホルツのヒドラよりも弱い。

Chris Birdバードの配列表記を使って\(\text{TREE}(3) > \lbrace3, 6, 3 [1 [1 \neg 1,2] 2] 2\rbrace\)、とした。[4]

弱いtree関数 編集

tree(n)弱いtree関数 を次のような1-labelled trees の列の最大長と定義する。

  1. 全てのグラフはすべての場所kでk+n以下の頂点を持つ。
  2. 列の中には 位相同型的埋め込み可能 である組は1つもない。

Adam P. Goucher はこの関数についての情報を発見した。

  1. tree(n)は急増加関数で\(\vartheta(\Omega^\omega)\)、BEAFでだいたい \(\{X,X (1) 2\} \&\ n\) の成長レベルを持つ。
  2. TREE(3) > treetreetreetreetree8(7)(7)(7)(7)(7)。

より大きい下限も見つかっている。 \(\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段重ね)とも表せる。[5]

\(\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)\) の値を決定するのは難しいが、その解の長さを持ったたくさんの最長列が存在する。

説明編集

グラフをそのまま書かずに可視化するのは難しいため、もっとコンパクトにグラフを表現する必要がある。(), [], {} と多くの種類のかっこで書かれた言語を考える。かっこたちはペアになっていて、互いにネストを形成できる。例えば、次のようなものがこの言語では「正しい」と言える。

[]
([])
{[()]()}
[(){[[]]}(){(())[]}]

文字列Aがあるとする。対応するかっこのペアをノードと呼ぶことにする。を、元のノードに1階層奥にネストされたノードであると定義する。例えば、Aを {[()()][][()]} であるとしゅると、{}の子は[]であり、()ではない。

ノードの持つ子が2つ以下ならば、それを削除可能と呼ぶ。例えば、Aを {[()()][][()]} であるとすると、全ての()、 最後と2つの[]は削除可能であるが、最初の[]と{}はそうでない。

もし文字列 A から文字列Bに、削除可能なノードを削除することで変換することが出来るならば、AはBへ縮約可能であるという。もしBであらわされるグラフがAであらわされるグラフと位相同型的埋め込み可能 である時に限り、文字列Aは文字列Bへ縮約可能である。

これらすべてを考え、TREE(k)と同じものを定義できる。次のような文字列列があるとする、

  1. k種類のブラケットを使っている
  2. 第1の文字列は最大1種類の括弧のペア、2つ目は2つのペア…となっている。
  3. どの文字列もその前の文字列の縮約グラフではない。

TREE(K)はこのような列の最大長である。

k=1, 文字列列は1つのみ、(). k=2なら、 文字列列は、 (),[[]],[] となる。

弱いtree関数 編集

上記と同様に定義すると:

  1. () 以外に括弧を使ってはならない。
  2. 始めの文字列は最大1 + k個の括弧のペア、2番目は 2 + k 個の括弧のペア…となっている。
  3. どの文字列も後の文字列から carvable ではない。

tree(K)はこのような列の最大長である。

出典 編集

  1. Adam Goucher, TREE(3) and impartial games
  2. Friedman's post on FOM mailing list
  3. How large is TREE(3)
  4. Chris Bird, Beyond Bird's Nested Arrays II, page 10
  5. How does TREE(3) grow to get so big? Need laymen explanation

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


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

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

Fandomでも見てみる

おまかせWiki