FANDOM


  • Hexirp

    この記事では私が考案したハイパー演算子の拡張を四つ紹介する。これらは普遍的な考え方を使ったものであるため同じものが別の人により考え出されている可能性が高い。

    この記事で元になっているハイパー演算子はゼロでない自然数 を超えても増加しつづける。

    (todo)

    ハイパー演算子とその拡張はゼロの場合にも整合的なある値を設定できる。以下の恒等式を満たすように定めればよい。

    (todo)

    しかし、弱ハイパー演算子ではできない。ハイパー演算子におけるテトレーションレベルになると期待される性質を満たすような値が存在しなくなってしまうからだ。

    全文を読む >
  • Naruyoko

    定義を書く練習1

    2019年4月15日 by Naruyoko

    メモリを、片側無限の大きさを持つ記号列とする。このとき有限側を左、無限側を右とする。

    メモリ内には有限個の非空白の記号と、残り無限に続く空白がある。

    メモリの初期状態は、以下の記号を持ちうる:

    0 - 定数 0、アリティ0

    S - 後続数、アリティ1

    D - Define、アリティ1(2?)

    f1, f2, etc. - 関数記号、アリティ1(DのFの場合アリティ0)

    nf1, nf2, etc. - 因数記号、アリティ0

    [空白] - 空白記号

    メモリの長さ(大きさでない)を、左端から最も右側の非空白の記号までの記号の数とする。

    また、これらのメモリをある値に計算するマシンがあり、以下のように計算する。

    1. 最も右側の非空白の記号から左側の空白をspliceし、

    2. もしメモリが空白記号を除いて逆ポーランド記法に則っていない場合、0を値として返し、

    3. そうでないならば、もしDがメモリ内にある場合、

    3.1. 最も左側のDの因数をL、それ以外(このDを含まない)をXとし、

    3.2. Lの内最も左側の記号をF、それ以外をRとすれば、

    3.3. もしFがfkの形でないとき0を値として返し、

    3.4. そうでないならばX内のすべてのFのインスタンスの集合をAとおき、

    3.5. Aの要素を、Fをアリティ1の関数としたとき、因数nFを対応する因数で置き換えたものをそれぞれ対応する位置ににspliceし、

    3.6. もしこの動作で得られたXのAがこれまでのこのDを解くAすべての和集合の要素と等しいAの要素を含む場合は0を値として返し、

    3.7. もし新しいAが空集合でないならば3.4.に戻り、

    3.8. このDとLをspliceし、

    3.9. もしDがメモリ内に存在するならば3.に戻り、

    4. そうでないならばすべての ……

    全文を読む >
  • Gaoji

    病的なたまねぎ

    2019年4月14日 by Gaoji


    (1) 二種類の矢印"→"と"←"とそれに関連した定義は以下の通りである。&,@は矢印を含まない任意の記号列である。

    • "→"を"右矢印"、"←"を"左矢印"という。
    • ある記号列Tについて矢印が"閉じている"とは、1. の下線部を満たしかつ 2. の下線部を満たすことをいう。
    1. Tに含まれる右矢印の集合からTに含まれる左矢印の集合への写像が全単射であり、かつ対応するすべての右矢印と左矢印について左矢印の右に右矢印がある。このように対応している左矢印の右かつ右矢印の左であるT上の位置に着目する。この位置にある記号列を、矢印の""と定義する。(でもこうすると、右矢印と左矢印に番号が振られることになる?)
    2. 数列Tに1つの矢印の組Sがあるとき、Sを構成する右矢印の左かつSを構成する左矢印の右であるT上の位置をSの""という。Sの中に記号列tがある時tはTの部分記号列で、SとSの中の記号列(ここではt)により構成される記号列を"構造(t,S)"という。ある記号列t'がSそのものではないかつSの中ではない場所にある時、t'はSの""にあるという。ここで、Tを構成する全ての組について、それぞれの組の中にある部分記号列にも1.が成り立つ。


    とりあえずここまで。ここより下は未編集。ここより上も未編集
    • 矢印が閉じていて、かつ矢印のみで記号列T矢印の一つ以上の組のみで構成されているとする。Tを構成する矢印の組について以下の言葉を決める。
    1. 組Sの外にTを構成する矢印の組がないとき、SをTの""という
    2. 組Sの中にTを構成する矢印の組がないとき、SをTの""という
    3. 組Sの中にある記号列T'について、T'の皮がS'であるとき、SをS'の""、S'をSの""という。
    4. 組SとS'が共通の親を持つとき、SとS'は" ……


    全文を読む >
  • P進大好きbot

    自作OCFとそれに伴う順序数表記に挑戦です。一応OCFの概説記事で以前OCFの例を書いたことはありますが、こちらは対応する順序数表記系がBuchholzの論文に書いてある順序数表記系の部分系になるように作ったのでほとんど何も工夫してません。今回はRathjenの弱マーロ基数を用いたOCFの論文に書いてあるっぽいけど読んだことがないので知らない。



    いる?



    全文を読む >
  • P進大好きbot

    uas的なもの

    2019年4月4日 by P進大好きbot

    mrna(伝)さんのuasっぽいものを演算だけで書いてみました。オリジナルを知らない人のためにも長々と書いていますが、オリジナルを知っている人は演算の章とFGHの章だけ読めば分かると思います。



    自然数と\((\)と\()\)と\(\oplus\)と\(\to\)と\(\uparrow\)のみからなる文字列が「uasの表記」であるという性質を以下のように再帰的に定義する:

    1. \(0\)はuasの表記である。
    2. uasの表記\(A\)と自然数\(a\)に対し、文字列\((A \oplus a)\)はuasの表記である。
    3. uasの表記\(A\)と\(B\)に対し\(A \to B\)はuasの表記である。
    4. uasの表記\(A\)と\(B\)に対し\((A \uparrow B)\)はuasの表記である。


    // \(-\)は見にくいので\(\oplus\)に変えました。また\(a+1\)と\((0)-(a+1)\)の役割がかぶっているので自然数を表記から外しました。例えば元のルールだと\(((A \uparrow B)-1) \to 0\)での値が定義されませんが、今回は定義されるように変更しています。

    ///*

    またあくまで文字列として処理しているので、\(A = 1 \to 2, B = 3\)の場合の\(A \to B\)と\(A = 1, B = 2 \to 3\)の場合の\(A \to B\)は区別できません。区別したい場合は

    1. \(0\)はuasの表記である。
    2. uasの表記\(A\)と自然数\(a\)に対し、文字列\(A \oplus a\)はuasの表記である。
    3. uasの表記\(A\)と\(B\)に対し\((A) \to (B)\)はuasの表記である。
    4. uasの表記\(A\)と\(B\)に ……



    全文を読む >
  • P進大好きbot

    「ESSSver.10」

    2019年4月2日 by P進大好きbot

    甘露東風さんのESSSver.10に類するものを項書き換え形式で定式化し直す試みです。



    // 構造という概念をあらかじめ定義します。まずはざっくりした定義です。文字列の処理をしやすいように入念にカッコで囲っています。

    \(0\)と\(1\)と\(+\)と\(\times\)と\((\)と\()\)と\(\langle\)と\(\rangle\)と\([\)と\(]\)のみからなる文字列が「構造」であるという性質を、以下のように再帰的に定める:

    1. \(0\)と\(\langle 0 \rangle\)は構造である。
    2. 構造\(X\)と\(Y\)に対し、文字列\(X + Y\)は構造である。
    3. 構造\(X\)と\(Y\)に対し、文字列\((X) \times (Y)\)は構造である。
    4. 構造\(X\)と\(Y\)と\(Z\)に対し、文字列\((X)[Y](Z)\)は構造である。


    // この書き方でも大体通じると思いますが、逆にどんな文字列が構造でないのかやや曖昧な表現なので↓のように集合の言葉で定式化するとより確実です。

    /*

    \(0\)と\(1\)と\(+\)と\(\times\)と\((\)と\()\)と\(\langle\)と\(\rangle\)と\([\)と\(]\)のみからなる文字列の集合\(S\)を以下を満たす最小の集合と定める:

    1. \(0, \langle 0 \rangle \in S\)である。
    2. いかなる\(X,Y \in S\)に対しても、\(X + Y \in S\)である。
    3. いかなる\(X,Y \in S\)に対しても、\((X) \times (Y) \in S\)である。
    4. いかなる\(X,Y,Z \in S\)に対しても、\((X)[Y](Z) \in S\)である。

    \(S\)に ……




    全文を読む >
  • Hanagami

    再帰的基本列系に慣れていないので, 自分の理解を試すために例を作ってみることにする.

    \(\epsilon_0\) 未満の順序数はカントール標準形というもので書けるそうなので, この記事では, これを文字列とアルゴリズムの言葉で書き直して, 最終的に\(\epsilon_0\)を上限とする再帰的基本列系を作ることを目指す.

    以下の手順で作る.

    1. 使う文字を固定し, 文字列の再帰的集合 T を定義する.
    2. T 上の再帰的関係 < を定義する.
    3. OT ⊂ T を定義し, 順序数表記 (OT,
    全文を読む >
  • やけたましゅまろ

    数式を練習したいので適当に巨大数を書いていきます.


    列とは以下のものを言う.

    • 0は列である.
    • 列と正整数の和は列である.(以後これを列の後続と呼ぶ)
    • 列の後続でない列は無限個の要素を持つ. そのような列\(\alpha\)の\(n\)番目の要素(0番目から)を\(\alpha[n]\)と表す.
    • 要素に列,非負整数のみを持つものは列である.
    • 列は上で定義されるもののみである.


    列 \(\alpha,\beta,\gamma\) に対して,SFGH関数 \(f_\alpha^\gamma(\beta)\) を以下のように定義する.

    • Rule.1) \(\gamma\) が列の後続で1ではないとき \(\delta+1=\gamma\) とおき, \(f_\alpha^\gamma(\beta)=f_\alpha^\delta(f_\alpha(\beta))\) である.
    • Rule.2) \(\gamma\) が列の後続でないとき \(f_\alpha^\gamma(\beta)[n]=f_\alpha^{\gamma[n]}(\beta)\) である.
    • Rule.3) \(\gamma=1\) 又は省略されているとき
      • Rule.3-1) \(\alpha=0\)のとき \(f_\alpha(\beta)=\beta+1\) である.
      • Rule.3-2) \(\alpha\)が列の後続のとき \(\delta+1=\alpha\) とおき, \(f_\alpha(\beta)=f_\delta^\beta(\beta)\) である.
      • Rule.3-3) \(\alpha\)が列の後続でないとき
        • Rule.3-3A) \(\beta\)が非負整数のとき \(f_\alpha(\beta)=f_{\alp ……


    全文を読む >
  • P進大好きbot

    曖昧さが少なくかつwell-definedになりやすい計算可能関数/計算可能数の定義の仕方の案です。

    まず計算可能関数/計算可能数の定義を表現する方法には、主に次の2通りがあります。

    1. プログラミング形式(入力に対する出力を計算する手順そのものを完全に記述する)
    2. 項書き換え形式(文字列の書き換え規則を羅列する)

    それぞれについて、どのように書くと良いかを提案致します。まずは双方の形式に適用可能な提案から行います。



    形式を問わずに推奨する提案をこちらに掲げます。



    色んな記号を使うことの多い巨大数界隈においては、色んな記号を使います。一方で

    • \(\langle a, x \rangle = a^x\)(\(a\)と\(x\)は自然数? だとしたら\(0^0\)って何? もしくはどちらかは正整数に限るの?)
    • \(\{0,x\} = x, \{a,x\} = \{a-1,\{a-1,x\}\}\)(\(a\)と\(x\)は自然数? でも\(a-1\)って出てきてるから、正整数に限るの?)

    のように動く範囲の不明瞭な変数が現れることが少なくありません。変数を使う際はきちんとその動く範囲を明示しましょう。



    何かを反復して書くことの多い巨大数界隈においては、省略記法を用いることが自然なことです。一方で、

    • \([1,x] = [0,\cdots [0,x] \cdots]\)(何回反復するの? まさかラヨ数回?)
    • \(a_0 = 0, a_1 = 111, a_2 = 22222, \ldots\)(\(a_3\)は何? まさかラヨ数?)
    • \(f_0(x) = x+1, f_1(x) = 2x, f_2(x) = x2^x, \ldots\)(\(f_3\)は何? まさかラヨ関数?)

    のように省略内容が復元可能でな ……







    全文を読む >
  • BashicuHyudora

    私の作ったBASIC言語による巨大数と加えて考えていることを発表します。(私の好きを自慢です、は誘いなのか。


    自然数が並ぶ形の数列で要素が端より小さいを見つけたらそこをコピーする。あの形から行列に 拡張は自分の中で第一歩。それが出来たらε_0の大きさになるだろう。これはグラハム数にならぶ 大きさの巨大数を意識できそう。
    刈った端より並んだ0で、1以上の要素が前にあってそこの前にその要素マイナス1を並ばさせる。 壁を乗り越すイメージ。
    (2,0,0,0)
    なら
    (1,1,...,1,1,2,0,0)
    こんな感じ。
    刈ったのが1以上では、これマイナス1の要素を並ばせる。多変数アッカーマン関数くらいの大きさを 意識して作った。 
    ベクレミシェフの虫が興味深いが、原始数列があるから沢山の拡張を私は作れた。だから小数列システムの 拡張、他のε_0システムを載せないとする。
    大きさがφ_ω(0)と特別好きです。個人的にこれで十分。原始数列システムの拡張となるものでも簡単で 好きです。 
    ベクレミシェフの虫の要素を超限順序数に拡張するアイデアは他の人もあった。それをΓ_0の数列を 作るのに応用させようと思って出来たかもしれない。
    解析すれば、
    (ω)=ε_0 (ω,0,ω,0,ω,...)=ε_0+ε_0+ε_0+...⇒(ω,1)=ε_0*ω (ω,1,0,ω,1,0,...)=ε_0*ω+ε_0*ω+...⇒(ω,1,1)=ε_0*ω^2 (ω,1,ω,1,ω,...)=ε_0*ε_0*ε_0*...⇒(ω,2)=ε_0^ω (ω,ω,ω,...)=ε_0^ε_0^ε_0^...⇒(ω+1)=ε_1 (ω+1,ω,ω+1,ω,ω+1)=ε_1^ε_1^ε_1^...⇒(ω+1,ω+1)=ε_2 (ω+2 ……











    全文を読む >
  • P進大好きbot

    巨大数界隈ではしばしば

    1. OCF(順序数崩壊関数)
    2. 順序数表記
    3. 順序数へ対応を持つだけの表記
    4. 基本列系を持つだけの表記
    5. 順序数に対する基本列系

    という互いに相異なる概念が用いられますが、これらは巨大数の解析が得意な人であっても混同しがちなものです。英語版巨大数wikiで「新しい順序数表記を作りました!」と宣言しながら順序数へ対応を持つだけの表記を載せているブログ記事も何度も見てきました。恐らくは

    • 順序数が何かを知らずに万能な呪文として使ってきたか(「順序数とは単なる記号だから説明に集合論を使うな」と主張する人さえ見かけます)
    • 順序関係の再帰性が何を意味するかを知らずに自動的に成り立つものと思い込んで使ってきたか(算術ではなく集合論で実際の順序数を用いて構成した非再帰な順序を持ち出してくることがたびたびあります)
    • 整礎性の役割を知らずに自動的に成り立つものと思いこんで使ってきたか(整礎性がないと超限再帰出来ないので順序数にも関数にも対応させられない場合がほとんどなのですが整礎性を気にしない人が少なくありません)
    • 順序数表記という言葉を何度も聞いたことがあるからその意味を何となく推測していたが、その定義を一度も読もうとしたことがなかったか

    といったところでしょう。そしてそういった人たちが大量に誤ったブログ記事を量産してきたため、新たにこれらを学ぶ人達が検索をする時に誤った情報を掴み同じような理解をしてしまいやすいという負の循環を生んでいるのだと考えられます。

    順序数表記は、単なる表記ではなく(原始)再帰的整列順序が定義されたものです。定義さえ知ってしまえば、UNOCFやBMSやその他の「順序数表記」と界隈で称されるものが明らかに順序数表記ではないことがよく分かります。実際、それらの定義において(原始 ……

    全文を読む >
  • Hexirp

    Coqで巨大数

    2019年3月10日 by Hexirp

    巨大数 Advent Calender 2018 2日目の『Coqを使った巨大数』を、ここで補足説明したいと思います。


    Coq とは形式証明支援システムです。つまり、証明を書くための言語と証明が正しいかどうかチェックする仕組みを持っています。これで書かれた証明は全て厳密に書かれており曖昧なところを生じません(機械的にチェックされている)。さらに、Coq はプログラミング言語でもあります。これはカリー=ハワード同型対応によって証明をプログラムとして表現しているからです。プログラミング言語として見たとき、全てのプログラムが停止するという性質を持っています(そうでないと、矛盾がある体系になってしまう)。

    Coq は、ベースの理論として pCIC (predicative Calculus of Inductive Constructions) を採用しています。Coq である関数を書けたとしましょう。すると「その関数は pCIC の下で well-defined である」ことが証明できたことになります。また、ある定理が証明できたとすると その定理が pCIC で証明できるということが分かることになります。重ねて言うと、それらは機械でチェックされているため誤りや抜けがないことが保証されています。


    最初に急増加関数を定義しています。この関数は全域的に定義することが出来ないので、それぞれの順序数に対する型クラスとして定義しています。その後、空集合と後者関数と極限に対して急増加関数がどう計算されるのか定義しています。

    そのあと、ここまで定義した操作を使って以下のような関数を定義しています。

    • \( F_0(n) = n+1 \)
    • \( F_{m+1}(n) = \lim \{ n, F_m(n) ……


    全文を読む >
  • BashicuHyudora

    バシク数

    2019年3月7日 by BashicuHyudora

    Bashicu matrixで評価出来たら(0,0,0)(1,1,1)(2,2,0)か?

    A=9:dim B[∞],C[∞],D[∞],E[∞],F[∞],G[∞,∞] for H=0 to 9 for I=1 to A for J=1 to I K=K+1:B[K]=I*I-2*(I-J) next next for K=K to 1 step -1 A=A*A for I=0 to K for J=I to K then if B[I] 全文を読む >
  • P進大好きbot

    この記事はInternet Explorerだとフリーズしやすいです。例えばGoogle Chromeが推奨です。






















    全文を読む >
  • Nayuta Ito

    //このページの二次創作。 //何をやっているかわかりやすくするためにコメントを追加した。 //更新がめんどくさいのでコメントの周辺だけ書く。

    以上で全単射 \begin{eqnarray*} \textrm{EnumNestArray} \colon \mathbb{N} & \to & \textrm{NestArray} \\ n & \mapsto & \textrm{EnumNestArray}(n) \end{eqnarray*} を得る。 //これはゲーデル数から入れ子配列を計算していることに相当する。 //計算例が必要な方は原文を読んでください。

    \begin{eqnarray*} f_{\{,\}} & = & (\textrm{Function},0) \\ f_{\{\}} & = & (\textrm{Function},1) \\ f_{(,)} & = & (\textrm{Function},2) \\ f_{\bigcup} & = & (\textrm{Function},3) \\ f_{\cup} & = & (\textrm{Function},4) \\ f_S & = & (\textrm{Function},5) \\ f_{\cap} & = & (\textrm{Function},6) \\ f_{\times} & = & (\textrm{Function},7) \\ f_{\wedge} & = & (\textrm{Function},8) \\ f_{(*)()} & = & (\textrm{Function},9) \\ f_{\mathcal{P}} & = & (\textrm{Function},10 ……

    全文を読む >
  • P進大好きbot

    反例アドベントカレンダー9日目のエントリーです。

    \(\textrm{Lim}\)で\(0\)でない極限順序数全体のクラスを表します。

    この記事では関数と言ったら写像\(\mathbb{N} \to \mathbb{N}\)を指し、関数全体の集合を\(\textrm{Func}\)と置きます。2つの関数\((g,h) \in \textrm{Func}^2\)に対し、その大小関係\(g < h\)を増大度の大小で定義します。すなわち、\(g < h\)であるとは、ある\(N \in \mathbb{N}\)が存在して任意の\(n \in \mathbb{N}\)に対し\(n > N\)ならば\(g(n) < h(n)\)となるということです。

    順序数\(\alpha\)で添字付けられた関数の族\((g_{\beta})_{\beta \in \alpha} \in \textrm{Func}^{\alpha}\)が線形階層であるとは、任意の\((\beta,\gamma) \in \alpha^2\)に対し\(\beta < \gamma\)ならば\(g_{\beta} < g_{\gamma}\)が成り立つということとして定義します。

    可算順序数\(\alpha\)とその基本列系 \begin{eqnarray*} \textrm{Lim} \cap \alpha & \to & \alpha^{\mathbb{N}} \\ \beta & \mapsto & (\beta[n])_{n \in \mathbb{N}} \end{eqnarray*} に付随するFGH。

      1. \(\beta[n] = \gamma_0 + \cdots + \gamma_{m-1} + \gamm ……
    全文を読む >
  • P進大好きbot

    5周年

    2018年12月5日 by P進大好きbot

    今日は英語版の創立10周年記念日だそうです。


    そこで、日本語版の創立はいつなのか気になってみて調べてみました。


    皆さんは、ご存知でしょうか?


    少し考えてみて下さい。


    答えは↓に書いてあります。






















    分かりましたか?


    そう、日本語版の方は、英語版の創立5周年記念日に創立されたようですね。


    ということは、ある1つの重要な事柄にお気付きではないでしょうか?


    簡単な演繹ですので、もう一度じっくり考えてみて下さい。


    答えは↓にあります。
























    もうお分かりでしょうか?


    まだの方は、もう少しお考え下さい。



























    もうお分かりですね?


    そう、その通りです。


    なんと今日は!


    日本語版の創立5周年記念日でもあるというわけですね!


    証明


    我々は巨大数を扱っているので、このような計算もお手の物です。


    おめでとうございます。

    全文を読む >
  • P進大好きbot

    Math Advent Calender 2日目の記事です。

    \(\textrm{ZFC}\)公理系の下で、\(\textrm{ZFC}\)公理系の無矛盾性を仮定して矛盾を導きます。(※よくあるネタです)

    \(L\)を\(\textrm{ZFC}\)集合論の言語とします。つまり可算無限個の変数記号\(x_0, x_1, x_2, \ldots\)と2つの二項関係記号\(=, \in\)を持つ、\(1\)階述語論理の形式言語です。\(L\)論理式の集合である\(\textrm{ZFC}\)公理系を\(A\)と置きます。仮定より\(A\)は無矛盾となります。

    \(A\)の下で\(\emptyset\)や\(\cup\)や\(\mathbb{N}\)における大小関係\( 0\)ならば、\(P_n\)は\(L\)論理式\(\forall x_{n-1}(P_{n-1} \to (x_n = x_{n-1} \cup \{x_{n-1}\}))\)である。 これは自然数のvon Neumann構成そのものですので、\(\exists x_n(P_n)\)は\(A\)の下で証明可能です。

    \(L\)に定数記号\(c\)を添加した形式言語を\(\hat{L}\)と置きます。

    \(\hat{L}\)論理式\(c \in \mathbb{N}\)を\(Q\)と置きます。

    各自然数\(n\)に対し、\(\hat{L}\)論理式\(\forall x_n(P_n \to (n < c))\)を\(R_n\)と置きます。

    \(\hat{L}\)論理式の集合である公理系\(A \cup \{\Psi\} \cup \{R_n \mid n \in \mathbb{N}\}\)を\(\hat{A}\)と置きます ……

    全文を読む >
  • Koteitan

    6月くらいに考えた Upper-Branch-Ignoring モデル (上枝無視モデル) というバシク行列(BM4)のヒドラ表現を紹介します。(バシク行列の展開ルールと、この記事内の数式については、バシク行列の数式的定義 を見てください。バシクさんのオリジナルの定義はこちらにあります。)


    BM4 の bad root 探索の方法については、Bubby3 さん、Ecl1psed276 さん、Alemagno12 さんが下記の記事で分かりやすく説明してくれています。

    • Bubby3, BM1 は期待より弱い -その修正方法
    • Ecl1psed276 and Alemagno12, BM2 のプログラムフリーな定義?

    これらの方法は内容は同じで、Ecl1psed276 さん、Alemagno12 さんはこの方法を sequence reduction method (数列削除法) と呼び、Bubby3 さんは upper-branch removing method (上枝削除法)と呼んでいます。

    Bubby3 さんは下記のように (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1) という行列を例に upper-branch removing method を使った bad root の見つけ方を説明してくれています。

    1. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    2. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    3. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    4. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    5. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    6. (0,0)(1, ……

    全文を読む >
  • P進大好きbot

    解析の練習です。浮笠さんのキマイラ数2号 Ver. 4を解析します。

    左辺の変数の最大値を\(M\)と置き、\(M \geq 3\)とする。\(X\)の長さを\(L\)と置き、\(L \geq 3\)とする。\(n \geq 3\)とする。左辺の変数末尾が\(a+1,b+1\)の式は数学的帰納法で導出している。左辺に\(n\)が現れる式は数学的帰納法で導出している。 \begin{eqnarray*} \textrm{Ch}[1](a,b) & \leq & \max \{a^b,a^a\} \leq M^M < f_3(M) \\ \textrm{Ch}[1](x_1,a,1) & = & \textrm{Ch}[1](x_1,a) < f_3(M) \\ \textrm{Ch}[1](x_1,1,b+1) & = & x_1^{x_1} \leq M^M < f_3(M) \\ \textrm{Ch}[1](x_1,1,2) & < & f_3(M) = f_3^1(M) \\ \textrm{Ch}[1](x_1,a+1,2) & = & \textrm{Ch}[1](x_1,\textrm{Ch}[1](x_1,a,2),1) < f_3(f_3^a(M)) = f_3^{a+1}(M) < f_4(M)\\ \textrm{Ch}[1](x_1,1,3) & < & f_3(M) < f_4^1(M) \\ \textrm{Ch}[1](x_1,a+1,3) & = & \textrm{Ch}[1](x_1,\textrm{Ch}[1](x_1,a,3),2) < f_4(f_4^a(M)) < f_4^{ ……

    全文を読む >
  • P進大好きbot

    巨大数たんアドベントカレンダー初日エントリー用の記事です。どうやら僕以外に誰も投稿しなさそうなので、遠慮なくこっそり事前公開してしまいます。

    全域計算可能関数\(\textrm{AC}_1(x)\)を定義します。誰か解析して下さい。

    ちなみに使って良い関数等は四則演算と自身が定義するものとカレンダー内で定義されたもののみというルールですので、冪乗や合成等も定義していきます。



    \(\mathbb{N}_{+}\)で正整数全体の集合を表す。


    正整数\(x\)と整数\(n\)に対し、正有理数\(x^n\)を以下のように再帰的に定める:

    1. \(n = 0\)ならば、\(x^n = 1\)である。
    2. \(n > 0\)ならば、\(x^n = x^{n-1} \times x\)である。
    3. \(n < 0\)ならば、\(x^n = \frac{1}{x^{-n}}\)である。


    正整数\(x\)と\(n\)に対し、正整数\({}^n x\)を以下のように再帰的に定める:

    1. \(n = 0\)ならば、\({}^n x = 1\)である。
    2. \(n > 0\)ならば、\({}^n x = x^{({}^{n-1} x)}\)である。


    写像\(f \colon \mathbb{N}_{+} \to \mathbb{N}_{+}\)と自然数\(n\)に対し、写像 \begin{eqnarray*} f^n \colon \mathbb{N}_{+} & \to & \mathbb{N}_{+} \\ x & \mapsto & f^n(x) \end{eqnarray*} を以下のように再帰的に定める:

    1. \(n = 0\)ならば、\(f^n(x) = x\)である。
    2. \(n > 0\)ならば、\(f^n(x) = f(f^{ ……





    全文を読む >
  • P進大好きbot

    全文を読む >
  • Kyodaisuu

    指摘された箇所と、どのような修正が必要になるのかをメモ。

    • 巨大数とビジービーバー
    • ビジービーバーQ&A: 計算不可能の鳥瞰図
    • 「いかなる再帰的理論でもビジービーバー関数の全域性を証明することができません」(p.241)は誤り。その前後の説明も見直しが必要。
    • 計算不可能関数のFGHによる近似はなくする。そのかわりに、ふぃっしゅ数バージョン4は「ふぃっしゅ関数バージョン4はω^(ω+1)*63次ビジービーバー関数程度の増加速度である」といったような表現を使う。
    • 無限時間チューリングマシンについては、とりマセブログを引用すれば紹介できる。
    • ACA_0がペアノ算術と同じ強さ、Z_2+PDとZFCとn-Woodin基数の証明力が同じ、など不正確な記述(proof-theoretic strengthという用語の勘違い?)
    全文を読む >
  • P進大好きbot

    巨大数たんシステムによる1ルール関数模索記事です。



    1ルールとは何かについては人それぞれの定義があると思うので、ここでは1つ定義を固定します。


    1. \(T\)を算術を含む理論とする。自然数なり実数なり数とみなしたい対象のクラスを\(T\)の中で固定し、それに値を持つ関数のみをここでは単に関数と呼ぶ。
    2. \(T\)における1ルール関数の定義文とは、関係記号(\(=,\neq,,\leq,\geq,\ldots\))がちょうど1つ出現する。



    \(=,\neq,,\leq,\geq\)は\(\leq\)のみで定義可能なので\(\leq\)の判定式さえあれば十分ですが、論理式の短縮および辞書作成を目的にそれらの判定式も与えておきます。

    また実数に対し適用可能な判定式を与えれば自然数に対しても適用可能なので十分ですが、代入する数によってたまたま他の判定式より短くなったりすることもあるので、適用範囲を狭めた場合特有の判定式も与えておきます。(いくつか判定式が重複しますが、各適用範囲ごとにまとめた方が見やすいので重複した判定式も略さず書きます)



    \(x \in \mathbb{R}\)とします。

    \begin{eqnarray*} \lim_{n \to \infty} \frac{1}{2^{x^2 n}} & = & \left\{ \begin{array}{ll} 1 & (x = 0) \\ 0 & (x \neq 0) \end{array} \right. \\ \lim_{n \to \infty} \frac{1}{2^{2^{x^2 n}}} & = & \left\{ \begin{array}{ll} 1 & (x \neq 0)\\ 0 & (x = 0) \end{array ……








    全文を読む >
  • GEBach

    \(\psi(0) = \psi_0(0) = 1\)

    \(\psi_{\beta}(0) = \Omega_\beta (\beta \ge 1)\)

    \(\psi_{\beta}(\Omega_{\beta+1}) = \epsilon_{\Omega_\beta+1}\)

    \(\psi(A+\Omega_{\beta+1})\)なら、\(\alpha\mapsto A+\psi_\beta(\alpha)\)の不動点をとり、一番外側に\(\psi\)をかぶせる。

    \(\psi(B + A\times\Omega_{\beta+1})\)なら、\(\alpha\mapsto B + A\times\psi_\beta(\alpha)\)の不動点をとり、一番外側に\(\psi\)をかぶせる。

    \(\psi(B + A^{\Omega_{\beta+1}})\)なら、\(\alpha\mapsto B + A^{\psi_\beta(\alpha)}\)の不動点をとり、一番外側に\(\psi\)をかぶせる。


    \(\psi(0) = 1\)

    \(\psi(1) = \lim[\psi(0), \psi(0) + \psi(0), \cdots] = \omega\)

    \(\psi(2) = \lim[\psi(1), \psi(1) + \psi(1), \cdots] = \omega^2\)

    \(\psi(\omega) = \psi(\psi(\psi(0))) = \lim[\psi(0), \psi(1), \psi(2), \cdots] = \omega^\omega\)

    \(\psi(\Omega) = \lim[\psi(0), \psi(\psi(0)), \psi(\p ……

    全文を読む >
  • GEBach

    練習

    2018年10月2日 by GEBach

    八卦数の中括弧配列表記の対応する順序数

    全文を読む >
  • Koteitan

    バシク行列システムの展開ルール BM4 の定義を数式だけで書いてみました。


    \begin{eqnarray*} \mathrm{巨大数:}~K&=&\mathrm{Bm}^{10}(9)\\ \mathrm{巨大関数:}~\mathrm{Bm}(n)&=&\mathrm{expand}((\underbrace{0,0,\cdots,0}_{n+1})(\underbrace{1,1,\cdots,1}_{n+1})[n])\\ \mathrm{発展ルール:}~\mathrm{expand}([n])&=&n\\ \mathrm{expand}({\boldsymbol S}[n])&=&\left\{\begin{array}{ll} \mathrm{expand}({\boldsymbol S}_0\cdots{\boldsymbol S}_{X-2}[f(n)])&(\mathrm{if}~\forall y~S_{(X-1)y}=0)\\ \mathrm{expand}({\boldsymbol G}{\boldsymbol B}^{(0)}{\boldsymbol B}^{(1)}{\boldsymbol B}^{(2)} \cdots {\boldsymbol B}^{(f(n))}[f(n)])&(\mathrm{otherwise})\\ \end{array}\right.\\ \mathrm{活性化関数:}~f(n)&=&n^2\\ \mathrm{行列:}~{\boldsymbol S}&=&{\boldsymbol S}_0{\boldsymbol S}_1\cdots{\boldsymbol S}_{X-1}\\ \mathrm{列:}~{\bo ……


    全文を読む >
  • 400011westo

    多層タワー関数

    2018年9月9日 by 400011westo
    全文を読む >
  • Kyodaisuu

    巨大数論のp.250-251で、ラヨ数の定義とZFC公理系の証明可能性について書いていますが、この記述は不正確のようなので、p進さんのブログを参照する形で書き直そうかと考えています。まずは、こんな感じで書いてみました。添削をお願いします。PDFも更新しています。


    ラヨ数は哲学の教授が考案したものであることから定義には問題がないものと多くの人が考えて、Wikipedia には英語版、日本語版だけでなく8ヶ国語版のページができています。榎宮祐「ノーゲーム・ノーライフ」9巻ではラヨ関数が使われています。しかし、数学者の間では、ラヨ数の定義は不十分なのではないかという意見があります。たとえばp進大好きbotは以下のような問題点を指摘しています。

    1. ラヨ数の定義には「二階述語論理に使われる公理系」と、ラヨ数の定義において式\(\phi(x_1)\)がある性質を「満たすような」自然数の集合を定義するために必要な「一階集合論の公理系」が指定されていない。
    2. 1については、いずれも一階述語論理のZFCであると解釈可能かもしれない。しかし、一階述語論理のZFCを使って再定式化したとしても、なお以下の点から定義が不十分である。
    3. ラヨ数の定義では、式\(\phi(x_1)\)がある性質を「満たすような」自然数の集合を定めている。ところがこれがどのような「モデル」で満たすという意味なのかが定められていないので、定義文になっていない。
    4. 3のモデルがなんらかの集合論のモデルであるとすると、「自然数を構成するための理論の公理系」と「モデルに課される公理系」がいずれもZFCであるとすれば、不完全性定理からモデルを明示する方法がなくなってしまう。
    5. 3のモデルが定義可能クラスであれば定義可能であるが、その場合は証明可能 ……

    全文を読む >
  • Kyodaisuu

    BM4

    2018年8月31日 by Kyodaisuu

    BM4の候補について、19:01, August 31, 2018版がうまく動かなかったのですが、このブログのコメント欄でバシクさんからの修正があり、19:07, September 1, 2018版でとりあえず動きました。

    • BASIC 版
    • Yabasic 直訳
    • Yabasic計算機

    テスト行列をBM2との比較スクリプトで比較したところ、テストした行列の中では3行まではBM2と完全に一致し、以下の2つのみが異なりました。

    (0,0,0,0)(1,1,1,1)(2,2,0,0)(3,1,1,0)(1,1,1,1)[2]


    計算機への移植は、これからします。

    (追記1)

    BM2.3 と BM4 の比較をしたところ、テスト行列では完全に一致しました。他の行列でも必ず一致するのかどうかはわかりません。

    (追記2)

    • basmatに入れました。テスト行列でBASIC版と完全に一致しました。
    • 計算機に入れました。

    (追記3)

    • koteitan によるとBM2.3とアルゴリズムは同じです。
    • 4行6列までのすべての標準BM4行列について、BM4=BM2.3を確認しました。
    • 同様の比較でBM2 と BM4 の展開が異なるパターンを抽出しました。
    全文を読む >
  • Kyodaisuu

    Akihiko Koga さんから、巨大数論の内容について以下の指摘を受けました。

    「巨大数論」の p118 の枠内の「整礎」の定義が間違っているように思います.枠内に書かれているのは整列集合の定義じゃないでしょうか? 「最小元」でなく「極小元」と思います.Wikipedia 等で「整礎」の定義を確認してみてください.

    「最小元」を「極小元」に修正する旨を返信したところ、さらに以下のように教えていただきました。

    修正案ですが,「最小元」から「極小元」に変えるのは良いのですが, その後の括弧の中も「極小元」に合わせた表現にする必要があります. 今は「最小元」の説明になっていますから.「極小元」の定義は https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88#%E6%A5%B5%E5%B0%8F にありますが,簡易な表現としては,
    二項関係 ≤ が整礎であるとは、集合 X の任意の空でない部分集合 A が極小元を持つことをいう(a0∈A が A の極小元であるとは、自分自身より真に小さい元が A に存在しないこと, つまり,a < a0 となる a∈A が存在しないことをいう)。

    くらいでしょうか.極小元の場合,最小元と違って複数あり得ますから, 「A の極小元 a0」と一意に決る表現は定義の部分では避けたいと思います.

    こうすると,あまり数学の熟練度のない読者には,整列集合の 「最小元」と整礎集合の「極小元」が結びつかなくなってしまう 可能性があるので,囲み記事の直後に

    全順序集合では極小元と最小元(その部分集合で一番小さい元)の概念は一致しますから、要するに、整列集合とはその任意の空でない部分集合に最小元 ……
    全文を読む >
  • Nayuta Ito

    非公開ページからの和訳・転載です。


    ここでは[-o-o…-o] nが


    となるので、元の式が証明された。

    全文を読む >
  • Kyodaisuu

    巨大数論2版2刷

    2018年8月8日 by Kyodaisuu

    巨大数論はインプレスの著者向けPOD出版サービスで出版していますが、当初は出版したものは修正不可能となっていましたが、あらためて調べてみると改修申請というのができるようになっていました。正誤表の項目も増えてきて、せっかくならば修正したものを購入したいという意見も出ているので、改修して2版2刷を発行することを検討します。改修の条件としては

    • 本文PDF(ページ数の増減は不可)
    • 表紙PDF
    • 裁ち落としの有無
    • 内容紹介
    • 検索キーワード
    • モノクロ書籍をカラーに変更したり、判型を変更したりは不可
    • 費用:5400円

    となっています。有料でもあり、今回の改修が最後の改修になるかもしれないので、改修の項目を検討します。

    なるべく、同じ版の同じページには同じ内容が書かれているようにしたいと思います。

    PDF版に、修正したものを随時アップしながらこのブログのコメントで確認していきます。

    なお、改修前のPDFファイルについては過去の版アーカイブ (ユーザー名 large パスワード number) あるいはGitHub レポジトリからアクセスできます。


    修正一覧

    • 正誤表と注釈の修正。p.202の追加はけっこう分量が多いので脚注にして、そのあとの式を少し削った。
    • p.44 Googology Wiki の言語が増えた。
    • p.118 ユーザーブログ:Kyodaisuu/極小元と最小元の違い
    • p.184-186 ユーザーブログ:Kyodaisuu/順序数講座 (10) フェファーマンのθ関数で検証したの記述の誤りを訂正
    • p.206〜 ペア数列プログラムの新しいバージョンで書き直した
    • p.226 強配列表記のNDAN以降が停止しないことの記述
    • p.223 BM4までの経緯をざっくりとまとめた
    • p.250-251 ユーザーブログ:Kyoda ……

    全文を読む >
  • Kyodaisuu

    バシク行列計算機に実装されているBM2は、バシクさんのBM2のBASICコードを私が読んでCに翻訳したものです。当時のブログの記事が2017年4月11日付となっていることから、その前日のバージョンを読んで作ったものだと推定したものです。

    今までこのバシクさんの元BASICプログラムを動かしたことがなかったので、BM3でやったのと同じようにして、バシクさんのプログラムを動かしてみて翻訳がきちんとできていたのかどうかを検証しておく必要があるかと思い、今さらながらやってみました。やり方の流れはユーザーブログ:Kyodaisuu/バシク行列バージョン3と同じです。

    まずはYabasic への直訳プログラムを作りました。これは、文法エラーをなくしただけのものです。

    次に計算過程を出力するプログラムを作りました。

    そしてテストスクリプトによって、この数列の全てを一括で計算結果の比較をしたところ、すべて一致しました。よって、翻訳が正確であることが示されました。もっとも、有限の数列を検証しただけなので数学的に証明されたわけではありません。

    実は、最初はまったく一致しなかったのでなんでだろうと思ったのですが、BM2sim.yab の78行目が

    for Q=1 to F D(Q)=0 next

    となっているところの、最初の Q=1 を Q=0 として

    for Q=0 to F D(Q)=0 next

    と直す必要がありました。BM2sim.yab の中には、コメントで修正を記入しました。検証はすぐに終わると思っていたのですが、このバグの発見に手間取ってしまいました。

    これは単純なバグ修正ということで、本質的にはバシクさんの意図したプログラムを改変していなかったということで許してください。

    …… 全文を読む >
  • Nayuta Ito
    1. により定義される整列集合への、単射であって全射でない写像が存在する、ということの形式的証明であって、複雑性≦dであるものが存在する
    2. そうでないとき、RWO(n,d)=0とする
    全文を読む >
  • P進大好きbot

    以前の記事では\(\textrm{ZFC}\)のPTOの証明論的類似を構成しました。同様の手法を用いることで、\(\textrm{ZFC}\)のPTOに対応する順序数表記を定義します。

    この順序数表記は標準的に強半順序の制限が再帰的強整列順序となるような標準形からなる再帰的部分集合を持ちませんが、\(\textrm{ZFC}\)の下で計算可能巨大関数を与えます。

    \(\textrm{ZFC}\)のPTOの証明論的類似に関する以前の記事と同様、形式言語\(L^{\textrm{M}}\)と\(\textrm{ZFC}\)公理系\(A^{\textrm{M}}\)で形式化された\(\textrm{ZFC}\)集合論\(T\)で考え、メタ理論の\(MT\)には\(\textrm{Con}(T)\)を課すことにします。

    元の記事は英文ですので少しずつ翻訳していこうと思います。誰か解析して下さい。



    I will define a map \(\textrm{RWO}\) sending an \(n \in \mathbb{N}\) to (the Goedel number of) a formula \(\textrm{RWO}(n)\) in an internal set theory such that the statement that \(\textrm{RWO}(n)\) is a definition of a recursive well-order on a recursive subset of \(\mathbb{N}\) admits a formal proof. Then \(\textrm{RWO}\) yields a non-recursive " ……



    全文を読む >
  • AAAgoogology

    巨大数関係でのTaranovskyのC表記の情報を探していましたが、巨大数関係では今のところHyp cos氏が最もTaranovskyのC表記に詳しいようです。Hyp cos氏は自身の作成した強配列表記の強さを評価するためにTaranovskyのC表記を用いています。また、強配列表記と他の順序数崩壊関数との比較も行っているので、強配列表記を介して間接的にTaranovskyのC表記と他の順序数崩壊関数との比較もある程度知ることができます。(私の予想でこの比較と合わない部分は撤回しました)

    Hyp cos氏による強配列表記とTaranovskyのC表記との比較のページ[1]ではTaranovskyのC表記よりもっと標準的な表記と比較してほしいというコメントもありましたが、Hyp cos氏によれば標準的な表記ではprimary dropping array notation (pDAN)の限界に届かないのでTaranovskyのC表記を用いているとのことでした。

    Hyp cos氏によるpDANの限界に対応する順序数のTaranovskyのC表記は、 \[ C(C(\Omega_22+C(\Omega_2+\epsilon_{C(\Omega_2,C(\Omega_22,0))+1},0),0),0)= \] \[ C(C(\Omega_22+C(\Omega_2+C(C(\Omega_2,C(\Omega_2,C(\Omega_22,0))),C(\Omega_2,C(\Omega_22,0))),0),0),0)= \] \[ \begin{array}{ccccccccccccc} & & & &\Omega_2& & & & ……

    全文を読む >
  • Hassium108

    数列・行列関連

    2018年7月8日 by Hassium108

    物置が広くなってきたので移しました。



    完成
    ×
    ×
    ×
    ×

    ×


    ◯?
    ×


    ×



    ?

     項を0の列に、セパレータを1に変換。


    \((3,3,0,2,1)→(0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,1,0,0)\)


    • 巨大数探索スレッド10の>>638
    • 巨大数探索スレッド11.75の>>1

    \(L_1+NZ\)

    \((1)=[1,0]={\omega}\)
    \((1,0)=[1,1]={\omega+1}\)
    \((1,0,0)=[1,2]={\omega+2}\)
    \((0,1)=[2,0]={\omega×2}\)
    \((0,1,0)=[2,1]={\omega×2+1}\)
    \((0,0,1)=[3,0]={\omega×3}\)
    \((1,0,1)=[1,0,0]={\omega^2}\)
    \((1,0,0,1)=[1,1,0]={\omega^2+{\omega}}\)
    \((0,1,0,1)=[2,0,0]={\omega^2×2}\)
    \((1,0,1,0,1)=[1,0,0,0]={\omega^3}\)
    \((1,1)=[1[0]0]={\omega^{\omega}}\)
    \((1,1,0)=[1[0]1]={\omega^{\omega}+1}\)
    \((1,1,0,1)=[1[0],1,0]={\omega^{\omega}+{\omega}}\)
    \((1,1,0,1,0,1)=[1[0]1,0,0]={\omega^{\omega}+{\omega^2}}\)
    \((0,1,1)=[2[0]0]={\omega^{\omega}×2}\)
    \((1,0,1,1)=[1,0[0]0]={\omega^{\omega+1}}\)
    \((1,1,0,1,1)=[1[0]0[0]0]= ……























    全文を読む >
  • P進大好きbot

    この記事では\(\textrm{ZFC}\)集合論を用います。算術を含む帰納的公理系でも同様の議論が可能であることを注意しておきます。

    それでは\(\textrm{ZFC}\)のPTOの「証明論的類似」を表す再帰的順序数表記を定義し、それに標準的な基本列を1つ定めます。

    これでも大きい順序数を表現できていると思いますが、まだ満足していないです。今後も更新して、強めつつもサラダビリティを減らしていきます。

    原文は英語の記事なため、少しずつ日本語に翻訳していきます。誰か解析して下さい。



    I will define a map \(\textrm{RWO}\) sending an \((n,d) \in \mathbb{N} \times \mathbb{N}\) to (the Goedel number of) a formula \(\textrm{RWO}(n,d)\) in an internal set theory such that if there is a formula \(F\) satisfying the following two conditions with respect to the notion of the complexity of a formal proof defined later, then \(\textrm{RWO}(n,d)\) also satisfies them:

    1. The statement that \(F\) is a definition of a recursive well-order on a recursive subset of \(\mathbb{N} \times \mathbb{N}\) adm ……


    全文を読む >
  • Kyodaisuu

    BM2.2のバグ修正

    2018年7月1日 by Kyodaisuu

    BM2.2 の計算にバグがありました。バグの修正ができました。

    バグの修正

    バシク行列計算機では、この修正をしました。この修正により、BM2.2の計算結果が変わる可能性があります。 オフライン版は、次回のリリースでこのバグが修正されます。


    BM2.2 で (0,0,0)(1,1,1)(2,2,2)(2,1,1)(3,2,2)[2] を計算しようとすると、Web版では問題なく動くのだけど、オフライン版で実行すると

    basmat -v 2.2 -o 1 -s 50 -t 3 "(0,0,0)(1,1,1)(2,2,2)(2,1,1)(3,2,2)[2]"

    のように実行したときに、うまくいくときは


    つまり、

    frame #0: 0x00000001000009a4 basmat`getParent(S=0x00000001001020e0, r=3, c=1073741824, nr=3) at basmat.c:55

    のところで c=1073741824 というのがなにかありそうです。

    その後はコメント欄にて。lldb の使い方を覚えたのが収穫。

    全文を読む >
  • Kyodaisuu

    BM2の復活

    2018年6月30日 by Kyodaisuu

    BM3をバシク行列計算機に実装したところ、早速Nishさんが無限ループを指摘、そしてそれを見たバシクさんがBM2の停止しないパターンを見つけるということになり、残っている(停止しないパターンが見つかっていない)のはBM2.2と未実装のBM2.3だけになりました。

    • 追記1:バシクさんによると、停止するというのは誤解でした。
    • 追記2:さらにその後、Bubby3さんが4行行列の停止しないパターンを見つけました。

    そして、早速バシクさんが新しいバージョンを作りました。

    バシク行列数 16:19, June 30, 2018‎ バージョン

    A=9:dim B[∞,∞],C[∞] for D=0 to 9  for E=0 to A   B[1,E]=1  next  for F=1 to 0 step -1   A=A*A   for G=0 to F    for H=0 to E     if B[F-G,H] 全文を読む >
  • AAAgoogology

    TaranovskyのC表記と他の順序数崩壊関数との比較を途中まで行いました。

    ユーザー:AAAgoogology/TaranovskyのC表記と他の順序数崩壊関数との比較

    英語版wikiのBoboris02氏のユーザーブログの比較と途中から一致しないので、どちらかに間違いがあるはずです。 私の比較に誤りがありました。現時点では\(\psi_{\Omega_1}(I_1)=\psi(\psi_I(I))\)は一致していますが、途中に一致しないところがあります。\(\psi\)関数の定義の違いによるものかもしれません。

    また、TaranovskyのC表記を木構造で表すとき、LaTeX表記を書くのは複雑な順序数になると大変なので、LaTeX表記を出力するpythonスクリプトを以下のページで公開しました。

    ユーザー:AAAgoogology/C表記の木構造のLaTeX表記のスクリプト

    全文を読む >
  • Kyodaisuu

    バシク行列計算機に実装されているバシク行列の最新バージョンは、バシクさんのオリジナル定義ではバージョン2です。それぞれの定義はユーザー:Kyodaisuu/バシク行列のバージョンにまとめました。バージョン2の後もユーザーブログ:BashicuHyudora/BASIC言語による巨大数のまとめでは定義が更新されているようなので、そろそろ計算機に入れようかと考えています。


    ユーザーブログ:BashicuHyudora/BASIC言語による巨大数のまとめの 21:32, June 12, 2018 に更新されたバージョンが、このブログ執筆時点での最新バージョンです。これを以下にコピーしました。

    • バシク行列最新バージョン:バシクさんの定義

    まずは BASIC の文法チェックをするために、Yabasic に翻訳しました。いくつかの文法エラーを直しました。それが以下のプログラムです。

    • バシク行列最新バージョン:yabasicへの翻訳

    変更した箇所は、

    1. Dim の中の∞を有限の値にしました。とりあえず文法チェックを通すための暫定です。
    2. 配列の [] を () にしました。例:B[1,E] → B(1,E)
    3. & を and にしました。
    4. | を or にしました。
    5. L.39: 計算順序を確定するために () を加えました。
    6. L.26, 39: endif を加えました。

    これで文法エラーはなくなりました。配列を有限にしているので配列が足りないというエラーになります(Redim で定義し直すこともできますが、結局メモリが足りなくなるだけなのでこのままでは計算は終了しません)。


    上の直訳プログラムでは計算の様子が見えないので、計算過程表示プログラムにしました。

    • バシク行列最新バージョン:計算過程表示

    このプログラムでは ……




    全文を読む >
  • AAAgoogology

    巨大な(再帰的)順序数の大きさを測るための「ものさし」としてTaranovskyのC表記がもっと使われてもよいと個人的には思うのですが、今のところ普遍的な「ものさし」としてはほとんど使われていません。 「ものさし」となる表記法には何が必要なのか、TaranovskyのC表記には何が足りていないのか、ということについて個人的な考えを述べます。

    まず、「ものさし」となる表記法には以下のような性質が必要であると思います。

    • 巨大な順序数を表記できる強力さ
    • 基本列や順序関係等の性質の分かりやすさ
    • 表記法の単純さ
    • 人間にとっての表記の見やすさ
    • 証明に裏付けされた厳密さ

    これらをヴェブレン関数やψ関数(の拡張)のような「ものさし」として使われている表記法と比較していきます。

    まず、強力さについてはTaranovskyのC表記が圧勝しています。ヴェブレン関数は2変数であればフェファーマン・シュッテの順序数\(\Gamma_0=\varphi(1,0,0)=\psi_0(\Omega^\Omega)=C(C(C(\Omega_1,\Omega_1),\Omega_1),0)\)未満の順序数を表すことができ、多変数であれば小ヴェブレン順序数\(\psi_0(\Omega^{\Omega^\omega})=C(C(C(C(0,\Omega_1),\Omega_1),\Omega_1),0)\)未満の順序数を表すことができます。ψ関数はブーフホルツのψ関数であれば竹内・フェファーマン・ブーフホルツ順序数\(\psi_0(\epsilon_{\Omega_\omega+1})=C(C(\Omega_2,C(C(0,\Omega_2),0)),0)\)未満の数を表すことができ、拡張されたψ関数であっても\(C(C ……

    全文を読む >
  • Kyodaisuu

    順序数講座の12回目です。前回は、ブーフホルツのΨ関数を解説しました。フェファーマンのθやブーフホルツのψではTFBが限界となっていますが、その先にはどのような順序数表記があるでしょうか。今回の講座では、Googology Wiki で議論されている TFB を超える構成的順序数の表記についてざっと見ていきます。今回は、私自身も十分に理解できていないということもあり、いつもの「気持ちの講座」をさらにざっくりとさせた「気持ちの気持ちの講座」となります。この講座をきっかけとして興味を持った人が自習できるように、なるべく参考サイトを示しながら進めていきます。

    Googology Wiki で順序数崩壊関数についての理解が深まったのは、2013年の Deedlit11 さんの Ordinal Notations と題する一連のブログ記事です。まずは、そのブログ記事をざっと眺めてみます。

    Ordinal Notations I: Up to the Schutte Klammersymbolen

    この回では、カントールの標準形とヴェブレン関数について解説されています。ヴェブレン関数については、多変数および超限変数のバージョンも紹介されています。

    Ordinal notations II: Up to the Bachmann-Howard ordinal

    バッハマン・ハワード順序数 BHO までの順序数崩壊関数について、3種類が紹介されています。

    1. Wolfram Pohlers のψ関数
    2. フェファーマンのθ関数
    3. θ関数を1変数にしたϑ関数

    そして、ψ関数について標準形と基本列を定義しています。

    Ordinal Notations III: Collapsing Higher Cardinaliti ……
    全文を読む >
  • Merliborn

    FGH revisited (2)

    2018年6月20日 by Merliborn

    ←前回:ユーザーブログ:Merliborn/Fast-growing hierarchy rivisited

    LöbとWainerによるオリジナルの急増加関数の定義には、現在我々がよく知る定義には存在しない関数ρα(n)が介在していました。これは極限順序数σに対して基本列の取り方が一意ではないために、Fσの単調増加性が自明とはならないために起こった現象でした。

    1970年の論文ではε₀まで、のちの研究ではさらに大きい領域までの順序数について、特定の基本列を取ることでρα(n)=nとしてよいことが分かっています。
    この記事ではε₀までの順序数について、Wainerの定義による急増加関数が全て単調増加であることを示します。
    基本的には順序数αについての超限帰納法によって証明されるのですが、各場合における証明のメカニズムを明示するために数段階に分割して記載しています。

    -- --

    全文を読む >
  • AAAgoogology

    Dmytro Taranovsky氏のC表記の解析結果をまとめたページ(ユーザー:AAAgoogology/TaranovskyのC表記の解析)を作成しました。 解析結果は十分な検証がされていないため、私のユーザーページの下に用意したページで公開しますが、 内容は他のページに転載していただいて構いません。 更新情報についてはユーザーブログの方に記載します。 解析結果のページのまえがきとほぼ同じ文章をこの記事に載せますが、詳細は解析結果のページを参照してください。

    Dmytro Taranovsky氏のC表記についての私の解析結果がすべて正しいとは限りません。 また、記述が不十分なところも多いので、理解できないところがあればコメントをお願いします。

    基本列の規則については推測するのが困難であるため、 プログラムで自動チェックした正しい基本列と比較して何度も修正しています。 現在の基本列の規則は\(\Omega_2\)を含む\(C\)が9個以下の順序数、\(\Omega_3\)を含む\(C\)が8個以下の順序数、 \(\Omega_4\)を含む\(C\)が8個以下の順序数、\(\Omega_5\)を含む\(C\)が7個以下の順序数に対して プログラムでチェックを行い、正しいことを確認していますが、 プログラムにバグがある可能性や、チェックしたよりも複雑な順序数に対しては基本列の規則に誤りがあるかもしれません。 誤りの実例を見つけた場合はその順序数をコメントで教えていただけるとありがたいです。

    私の解析結果で特に意義があると思われるのは次の3点です。

    1. 括弧が入れ子になって読みづらくなるのを、木構造で見やすく表記したこと。
    2. \(n\)-built from belowに相当する定義をす ……
    全文を読む >
  • Kyodaisuu

    順序数講座の11回目です。前回は、フェファーマンのθ関数を紹介しました。

    今回の講座では、ブーフホルツがフェファーマンのθ関数を改良して1986年に次の論文で発表したψ関数を紹介します。

    Buchholz, W. (1986) "A New System of Proof-Theoretic Ordinal Functions". Annals of Pure and Applied Logic, 32; 195-207.

    論文の最初のところだけ読んでみます。

    この論文では ψν (ν ≤ ω) という順序数の関数族を発表する。これは大きな構成的順序数を表記するこれまでの中で最も簡単な方法のようである。これらの関数はθ関数の簡略化バージョンであるが、同じ強さを持つ。(原文: In this paper we present a family of ordinal functions ψν (ν ≤ ω), which seems to provide the so far simplest method for denoting large constructive ordinals. These functions are a simplified version of the θ-functions, but nevertheless have the same strength as those.)

    つまり、θ関数よりも「簡単なのに同じ強さ」というセールスポイントで発表された関数です。これがその定義です。


    定義(ブーフホルツのψ関数)
    ブーフホルツのψ関数 ψν(α) = ψνα を次のように定義する。
    1. 順序数 ν, α に対して、集合 Cν(α) を次のように定める。
    2. Ων よりも小 ……


    全文を読む >
  • P進大好きbot

    サラダ注意。

    当初は\(\Omega\)収束点を崩壊させるつもりが崩壊させずにそのまま使ってしまったため、FGHで\(\omega\)になるという不具合がありました。今度こそちゃんと崩壊させたので\(\psi_0(\psi_I(0))\)に到達してくれたと思います。




    何の工夫もなく翻訳したので、ものすごく長ったらしくてすみません。ちなみに使ったのはBuchholzのオリジナルのψ関数ではなく英語版にある拡張の方です。\(\Omega\)収束点を崩壊させています。

    ただしそのまま翻訳したとは言っても、

    • 順序数側の加法を降順に直すステップの順序数表記における記述方法が思い付かなかったため、降順でない加法も許している。
    • 原論文にある\(G\)に関する制約を一切課していないため、\(G\)に関して下降するような\(\psi\)の適用を許している。

    という事情で重複のある表記となっています。それに起因してどれくらい弱くなるのかは分かりません。

    そして順序数崩壊関数から順序数表記を構成する方法はBuchholzのオリジナルの構成\(\psi \mapsto OT\)を使っています。これが拡張の方でも機能しているのかはよく分かりません。





    \(5\)種類の記号\((\)と\()\)と\(\langle\)と\(\rangle\)と\(,\)のみからなる文字列が「配列」であるという概念と「組」であるという概念を、以下のように帰納的に定める。

    (1) \(()\)は配列である。

    (2) 配列\(X_1,X_2\)に対し、\(\langle X_1, X_2 \rangle\)は配列であり組である。

    (3) 組\(X_1, \ldots, X_m\)(\(1 \leq m < \infty\))に対し、\((X_ ……






    全文を読む >
  • Kyodaisuu

    順序数講座の10回目です。前回は、ヴェブレン関数の定義をしました。

    1. φαβ は 0 と + とφγ
    全文を読む >