Fandom

巨大数研究 Wiki

ラヨ数

549このwikiの
ページ数
新しいページをつくる
コメント4 シェアする
ラヨ関数
計算不可能関数
急増加関数 \(f_{\gg \omega_\alpha^\text{CK}}(n)\)

ラヨ数 (Rayo's number) は、Agustín Rayo と Adam Elga の巨大数決闘で Agustín Rayo が名付けた、最大の巨大数である[1][2]。ラヨ数は、ラヨ自身の言葉によれば、「一階の集合論(一階述語論理)の言葉でグーゴル個以内の記号で表現できるいかなる有限の正の整数よりも大きな最小の正の整数」である。

「グーゴル」を任意の正の整数とすれば、非常に増加速度の大きいラヨ関数 \(\text{Rayo}(n)\) を得ることができる。ラヨ関数は計算不可能であり、チューリングマシンによって(そして、チャーチ・チューリングのテーゼによれば、いかなる現代のコンピュータを使っても)、 \(\text{Rayo}(n)\)あるいは \(\text{Rayo}(10^{100})\) の値を、無限の時間とメモリを使わずに計算することはできない。さらに、神託機械あるいはオーダーnのビージービーバー関数を使っても計算出来ない。

ラヨ関数の強さは、「現代数学の基礎そのもの」に対して対角化をしている、というところから来ている。\(\text{Rayo}(n)\)よりも有意に強い簡単なシステムを構築することはとても難しく、いまだ作られていない。

定義 編集

\([\phi]\) と \([\psi]\) を ゲーデル数化された式 として、\(s\) と \(t\) を変数設定とする。 \(\text{Sat}([\phi], s)\) を次のように定義する。

∀R {
  {
    ∀[ψ], s: R([ψ],t) ↔ ([ψ] = "xi ∈ xj" ∧ t(xi) ∈ t(xj))
                      ∨ ([ψ] = "xi = xj" ∧ t(xi) = t(xj))
                      ∨ ([ψ] = "(¬θ)"    ∧ ¬R([θ], t))
                      ∨ ([ψ] = "([θ]∧ξ)" ∧ R([θ], t) ∧ R([ξ], t))
                      ∨ ([ψ] = "∃xi(θ)"  ∧ ∃t′: R([θ], t′))
                      (where t′ is a copy of t with xi changed)
  } ⇒ R([ϕ],s)
}

\(n\)個以下の記号を持ち、自由変数がただ1つ\(x_1\)であり、そして次のすべての性質を満たすような式 \(\phi(x_1)\) が存在する時に、自然数 \(m\) を「\(n\)個の記号でラヨ命名可能である」とする。

  1. \(Sat([ϕ(x1)],s)\) であるように \(x1:=m\) とする変数設定\(s\) が存在する。
  2. 任意の変数設定\(t\) に対して、 \(Sat([ϕ(x1)],t)\) なら\(t\) は \(x1=m\) を含む。

そして\(\text{Rayo}(n)\)は\(n\)個の記号でラヨ命名可能なすべての数より大きい最小の数である。

説明1 編集

変数設定は、 \((3, 2, 6, 1/2, \{4, \pi\}, \text{カナダ}, \omega, 65, \ldots)\) のようなオブジェクトの無限の連続である。は、変数設定に関する文章である。たとえば、「3つ目の変数は2つ目の変数に対して素である」「2番目の変数は3.2以外のすべての実数の集合である」というような文章である。

ラヨは、式を記述するためのマイクロ言語を、このように厳密に定義した。

  1. "ab" a番目のオブジェクトはb番目のオブジェクトの要素である
  2. "a=b" a番目のオブジェクトはb番目のオブジェクトと等しい
  3. "(¬e)" 式eの否定
  4. "(ef)" 式eと式fの論理積(and)
  5. "∃a(e)" 式eが真となるようにa番目のオブジェクトを変えることができる

たとえば、"1∈2"という式を考える。これは「1番目のオブジェクトは2番目のオブジェクトの要素である」ということであるから、(リンゴ, すべての果物の集合, \(\ldots)\) という変数設定をすれば、式の評価は「真」となる。なぜならば、リンゴは果物の1種であるからである。もし、 (チーズ, すべての果物の集合, \(\ldots)\) という変数設定をすれば、チーズは果物ではないため、式の評価は「偽」となる。

さらに複雑な例を示す。 "(¬∃1(1∈2))" これは、「1番目のオブジェクトが2番目のオブジェクトの要素である、という条件を満たすように、1番目のオブジェクトを変えることはできない」ということである。このような条件は、2番目のオブジェクトが空集合の時に成り立つ。たとえば、 \((3, \{\}, \ldots)\) というような変数設定である。この時、1番目のオブジェクトである \(3\) の値をいかように変えても、空集合の要素とすることはできない。

ある変数設定がされたときにある式が真であれば、その変数設定がその式に対して「適合する」と言うこととする。

ここでようやく、主要概念である「ラヨ命名可能」を次のように書くことができる。ただし、式に含まれる記号の数に関する制限は無視する。

ある式\(\phi\)が存在し、「式\(\phi\)に適合するようなあらゆる変数設定に対して、1番目の引数が \(m\) であり、そのような変数設定が少なくとも1つは存在する」という条件を満たす時、\(m\)は「ラヨ命名可能」である。

まずは、0がラヨ命名可能であることを示す。順序数の体系では、\(0 = \{\}\) と定義される(順序数の定義参照)。1つ目の要素が必ず空集合 \(\{\}\) となるような式 \(\phi\) を考える必要がある。その1つが "(¬∃2(2∈1))" = "変数2が変数1の要素となるような変数2を選ぶことができない" = "変数1の要素を選ぶことができない" = "変数1の要素はない" である。

さて、次は \(1 = \{\{\}\}\) をラヨ命名する方法を見つける必要がある。まずは、上記と同じ方法で "(¬∃3(3∈2))" として変数2を空集合とする。そして、変数1は \(\{\{\}\}\) であり、変数2の \(\{\}\) を要素に持つ集合であるから、 "2∈1" が必要である。変数1が他に要素を持たないことは、 "(¬∃3((3∈1∧(¬3=2))))" = "変数3が変数1の要素であるが、変数2と等しくない、という条件を満たすように変数3を選ぶことができない" = "変数3が変数1の要素であれば、必ず変数2と等しい" = "変数1に要素が存在する場合には、変数2は変数1の唯一の要素である" と表現できる。これら3つの文を "and" で結んで、 "(((¬∃3(3∈2))∧2∈1)∧(¬∃3((3∈1∧(¬3=2)))))" という式を得る。これが、1をラヨ命名する式である。

このパターンを続けることで、自然数を1つずつ定義することができる。この方法では、 \((9n^2 + 47n + 20)/2\)個の記号で自然数 \(n\) を命名することができる。数字が大きくなれば、再帰的操作を定義することができるようになり、より大きな数字を少ない文字数でラヨ命名できるようになる。十分に大きな数字に対しては、指数を計算するために使われる記号の数は我々が自然に思いつく方法よりも少ない文字数で可能となるであろう。

なぜラヨ関数が計算不可能なのであろうか?集合論は無限集合を取り扱う。たとえば、 "(¬∃2((¬2∈1)))" という式で、変数2はあらゆる集合を含む universal set である。困難ではあるが、急増加関数や他の階層における順序数を定義して、変数に入れることも可能である。フォン・ノイマン宇宙全体を反復計算するようなアルゴリズムは「絶対に」あり得ない。

説明2 編集

ベリーのパラドックスから説明を始める。

xを英単語12個以内で定義できない最小の自然数であるとする。すると、xは "the smallest natural number not definable using at most twelve English words" と、英単語12個で定義できる。このように、xを12文字以内の英単語で定義できたので、xは英単語12個以内で定義できない最小の自然数ではない。これは、矛盾である。

このパラドックスが生じる原因は、「定義可能である」という言葉の曖昧さにあり、もっと根本的には、英語という言語そのものの曖昧さにある。ラヨ関数は、「英語」のかわりに「一階の集合理論」(FOST)と言われる形式体系を使うことによって、このような数学的な欠点を回避している。FOSTはフォン・ノイマン宇宙を領域(domain)とする一階述語論理の体系である。具体的には、FOSTは集合の要素を決定すること、領域上で量化すること、そして論理演算子を適用することができる。実際にどのように動くかという詳細は、上に記されている。

ベリーのパラドックスが生じないように、次のように定義する。

FOSTの表現でn個以内の記号で一意に特定できない最小の自然数

これは、次の Rayo(n) の表現を少し書き換えたものである。

FOSTの表現でn個以内の記号で一意に特定できるいかなる自然数よりも大きな最小の自然数

定義可能性の記述が形式体系に置き換えられているため、パラドックスがなくなっている。FOSTは、他の形式体系と同じように、Tarski's undefinability theoremが成り立ち、真偽判定や、ましてや定義可能性の判定を記述することができないため、英語の中に英語を含めるように、FOSTの中にFOSTを含めることができない。

歴史 編集

ラヨとエルガの巨大数競争は、Scott Aaronson の記事に基づいている。

2013年の1月に、 Adam Goucher は \(\text{Rayo}(n)\) の増加速度は急増加関数で \(f_{\omega^\text{CK}_\omega}(n)\) に相当すると報告をした[3]。ここで、 \(\omega^\text{CK}_\omega\) は admissible ordinals の数列 \(\omega^\text{CK}_1\), \(\omega^\text{CK}_2\), \(\omega^\text{CK}_3\), ... の極限で、 \(\omega^\text{CK}_1\) は チャーチ・クリーネ順序数 である。そして、彼はクサイ関数を考案し、その増加速度は急増加関数で \(\alpha \mapsto \omega_\alpha^\text{CK}\) が成り立つ最初の順序数であると信じられている。

しかしながら、この主張は誤りであることが分かった。誤りの原因は、 Goucher がラヨ数の定義を「n文字の一階算術(ペアノの公理)で一意に表現できる最大の整数」であると勘違いをしていたことであった。一階算術よりも二階算術(Second-order arithmetic)はもっと強く、一階集合理論はさらに強い。一階算術の議論領域は自然数で、一階集合理論の議論領域はフォン・ノイマン宇宙の集合全体であると定義されている。したがって、ラヨ関数はほぼ間違いなくクサイ関数よりも強く、 \(\text{Rayo}(n)\) の急増加関数による増加速度の見積りは、第一定義不能順序数に関係しているのではないのかという推測もあるがはっきりとせず、まだ探求中である。

関連項目 編集

出典 編集

  1. Big Number Duel
  2. Profs Duke It Out in Big Number Duel
  3. Goucher, Adam. The Ξ function. Retrieved 2013-03-21.

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


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

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

Fandomでも見てみる

おまかせWiki