FANDOM

  • Hex347

    ラヨ数に関するメモ

    2016年6月26日 by Hex347

    メモ。正しいかどうかは分からないので注意してください。


    ユーザーブログ:Kyodaisuu/偽ラヨ数という物があることを初めて知った。最初はなぜラヨ数と違いがあるのか分からなかったが、偽ラヨ数、ラヨ数でいう「グーゴル個以内の記号で表現できる正の整数」の分布は連続的ではなく隙間があると考えると納得できた。


    自分は、ラヨ数でいう一階集合理論(FOST)は単にZFC集合論の事だと思っていたが、本当は一階述語理論によって定義された、述語関数「\( = \)」「\( \in \)」を含む理論の事であった。

    それを聞いて、「空集合などが含まれていると保障されていないといけないのでは?」と思ったが、答えがラヨ数の記事に書いてあった。説明2の節に「FOSTはを領域(domain)とするの体系である。」とある。体系と書いてあることから、ZFC集合論のようなただ一つの理論に限定されたものではないことが分かる。また、「フォン・ノイマン宇宙を領域とする」と書かれていることから、FOSTは少なくとも、フォン・ノイマン宇宙に含まれる必要がある集合の存在が保障されていることになる。


    ユーザーブログ:Hex347/アッカーマン関数の簡潔な表記でだらだら書いていたハイパー演算子の拡張(今は削除済)が、自分で納得できるものになったのでメモしておく。配列表記などで既に実現されたアイデアの気もするが気にしないでおく。

    ハイパー演算子のペア数列的表現。ある数xを取り、括弧を使ってスタック的な記法で表す。
    スタックがない場合の値の取り出し(=零変数版) [a]=a
    ここから括弧の連続を...で表す。
    一変数版 ...()[a]=...[a+x]
    二変数版 ...(1)[a]=...[a+x] ...(y)[1]=...[x] .. ……






    全文を読む >
  • Hex347
    この記事は執筆中です。

    この関数は計算不可能な関数にみられる共通点に着目したアイデアにより作られました。まず、非常に大雑把に言ってしまえば、計算不可能な関数は次のように表現できると思っています。

    • ビジービーバー関数は「x文字以下のプログラムで表現できる自然数」の内で最も小さい物を返します。
    • クサイ関数は「x文字以下の、神託コンビネータ\(Ω\)を追加したSKIコンビネータ計算(=プログラム)で表現できる自然数」の内で最も小さい物を返します。
    • ラヨ数を生成する関数は「x文字以下の、一階集合理論(FOST)の言語で表現できる自然数」の内で最も小さい物を返します。

    このように書くと、「x文字以下の〇〇で表現できる自然数」という共通点が見られます。〇〇の表現力が高いほど、この形式の関数の増加速度は速くなると考えられます。つまり、この推測が正しければ、〇〇の表現力を一階集合理論(FOST)よりも高めると、ラヨ数を生成する関数よりも増加速度が速い関数を作れると考えられます。この方法で作られた関数がビッグフットを生成する関数だと認識しています。

    Hex関数は、上の「x文字以下の〇〇で表現できる自然数」という共通点に関する認識が正しいことを前提にした関数です。つまり、これが正しくなければ崩壊する「取らぬ狸の皮算用」的な関数です。ただ、作ってしまったので、このまま正しいとして進めていきます。

    また、この関数は、「理論とは、論理式に関する記号と公理規則と推論規則しか定義されていない一階述語論理に、対象記号と関数記号と述語記号を付け加えたものである。」という認識に依存しています。


    まず、「x文字以下の〇〇で表現できる自然数」の〇〇に何を入れるかですが、「一階述語論理において、自然数を表現できる理論全て」を入 ……


    全文を読む >
  • Hex347

    この記事は執筆中です。

    アッカーマン関数は理解しづらいなと思っていました。しかし、考えを巡らせていたところ、アッカーマン関数を簡潔な表記で表す方法を見つけましたのでここにメモします。


    アッカーマン関数は非負の整数に対して次のようにして定義されます。


    このくらいにしておきます。さて、2の壁がなくなったとき、大量の1が出来ました。1の壁は積み重なった0の壁を作り、2の壁は積み重なった1の壁を作り、nの壁は積み重なったn-1の壁を作るというのが、もう一つの規則性です。

    このリストのような表記法で計算するというのは、「アッカーマン関数」「スタック」と検索すれば出てくる手法です。

    全文を読む >
  • Hex347

    新しい関数の提案

    2016年2月26日 by Hex347
    恥ずかしいことに、この記事には大きな間違いが含まれています。

    少なくともラヨ数より大きい数を作る方法を思いつきました。なので、ここに書き留めておきたいと思います。


    ラヨ関数は一階述語論理の上に構築されたZFC集合論を基礎として作られています。しかし、集合論はそのほかにも選択公理を認めない集合論、巨大基数が存在するという公理を付け加えた集合論、連続体仮説を否定するか肯定するかのどちらかの公理をZFC集合論に付け加えた集合論など様々なものがあります。 このことから、一階述語論理で表せる論理そのものを対角化した、「一階述語論理の上でx文字以内で構築できる論理で表すことが出来る数を返す関数f(x)」は明らかにラヨ関数よりも強いと考えられます。

    ただし、論理はさまざまな種類があるので、それによって作られる物にはさまざまなものがあります。それらの中には数とはとても呼べないようなものも含まれています。これは難しい問題ですが、ペアノの公理を満たすものだけを数と定義すれば、うまく数と呼べないものを除けるのではないのでしょうか。

    これを考慮した定義を言葉で表すのは難しいので、架空的な計算過程を書くことで定義とします。

    1. 一階述語論理を基礎として、その論理を定める物(公理や推論規則など)がx文字以内で構築できる論理全体のリストOを求める。
    2. Oのうち、ペアノの公理を満たす構造を定義できない論理を除いたリストQを求める。
    3. Qを構成する論理すべてに次の操作をする。
      1. この論理を使って定義できるペアノの公理を満たす構造全体のリストNを求める。
      2. Nを構成する構造すべてに次の操作をする。
        1. この構造である物のうち、この論理を使ってx文字以内で定義できる物全体のリストRを求める。
        2. リストRを構成する物のうち、「これより小さい物Aとこ ……

    全文を読む >

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


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

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

FANDOMでも見てみる

おまかせWiki