配列システム
- 1 第k配列数
- 2 第1配列システム
- 2.1 概要
- 2.2 表記
- 2.3 計算法
- 2.4 評価
- 3 第２配列システム
- 3.1 概要
- 3.2 表記
- 3.3 計算法
- 3.4 評価
- 4 第３配列システム
- 4.1 概要
- 4.2 表記
- 4.3 計算法
- 4.4 評価
- 5 小拡張第3配列システム
- 5.1 概要
- 5.2 表記
- 5.3 計算法
- 5.4 評価
第k配列システムに対して\(A_k(n)=nL_k[1,0,0,…(0がn個)…,0]\)とし、第k配列数を\(A^{10}_k(10)\)とする。
最も単純な構造の配列。
・NFO型（F＝\("L_1"\)）
・配列構造
例：\(3L_1[2,3,0]\)
・\(Z\)：０個以上の０
・\(\#\)：０個以上の非負整数
(1) \(nL_1[\#,a]=(n+a)L_1[\#,0]\)
(2) \(nL_1[Z]=n\)
(3) \(nL_1[\#,a+1,0,Z]=nL_1[\#,a,n,Z]\)
\(nL_1[1,0,0,…0]\approx f_{\omega}(n) \)
\(A^{10}_1(10)\approx f_{\omega+1}(10)\)
結合構造を導入することにより、多変数アッカーマン関数やBEAFの構造を表現。
・NFO型（F=\("L_2"\)）
・配列構造＋結合構造
例：\(2L_2[1,0,5][2,1][1,4][3]\)
・\(Z\)：０個以上の０
・\(\#\)：０個以上の非負整数
・\(□\)：１個以上の配列
・\(n\)：変数
・右端の配列から計算を行う。
(1) \(nL_2□[Z]=(n+1)L_2□\)
(2) \(…
順序数列ゲーム
- プレイヤーは前のプレイヤーが言った順序数より小さい順序数を言う
- ０を言ったら終了
というルールのゲームは、必ず有限回で終了し、各ターンにてプレイヤーが言える順序数にをうまく制限すればターン数の上限が生まれる。
- 1 例：2変数関数ゲーム
- 2 位相同型的埋め込み可能
- 3 サブツリー関数
- 4 多重配列列
プレイヤーは下の3つの関数を組み合わせて表せる順序数を言うことができる。
ただし、kターン目で使用可能な関数の個数は合計k+n個までで、変数は1~k+nまでの自然数と\({\omega}\)である。
\(A({\alpha},{\beta})={\alpha+{\beta}}\)
\(B({\alpha},{\beta})={\alpha×{\beta}}\)
\(C({\alpha},{\beta})={\alpha^{\beta}}\)
例(n=1)
\(C({\omega},C({\omega},{\omega}))={\omega^{\omega^{\omega}}}\)・・・1ターン目なので、1＋1個の関数を使える
\(C({\omega},C({\omega},C(3,3)))={\omega^{\omega^{27}}}\)・・・2ターン目なので、2+1個の関数と2+1以下の自然数を使える
\(C({\omega},C({\omega},B(4,B(3,2))))={\omega^{\omega^{24}}}\)・・・3ターン目なので、3+1個の関数と3+1以下の自然数を使える
\(C({\omega},B(C({\omega},A(B(5,4),3),5)))={\omega^{\omega^{23}×5}}\)・・・4ターン目なので、4+1個の関数と4+1以下の自然数を使える
・
・
・
nに対するターン数…
FGHと超限順序数
「巨大関数に超限順序数を突っ込んで巨大な順序数を作る」というのは簡単かつ効率的なやり方のように思えるが、BEAFがそうであるようにうまくいかないことが多い。このブログ記事ではFGHに超限順序数を入れたシステムについて考える。
- 1 0～有限順序数
- 2 ω～
- 3 SGH
- 4 数列システム
- 5 拡張(?)グッドスタイン数列
- 5.1 \(a=0\)
- \(f_0({\beta})={\beta+1}\)
- \(f_{\alpha+1}({\beta})=f^{\beta}_{\alpha}({\beta})\)
- \(f^{\gamma+1}_{\alpha}({\beta})=f_{\alpha}(f^{\gamma}_{\alpha}({\beta}))\)
- \(f^{\gamma}_{\alpha}({\beta})[n]=f^{\gamma[n]}_{\alpha}({\beta})\)
- \(f_0({\omega})={\omega+1}\)
- \(f_1({\omega})=f^{\omega}_0({\omega})={\omega×2}\)
- \(f^{\omega}_0(f_1({\omega}))={\omega×3}\)
- \(f_1(f_1({\omega}))=f^{\omega×2}_0({\omega×2})={\omega×4}\)
- \(f_2({\omega})={\omega^2}\)
- \(f_1(f_2({\omega}))={\omega^2×2}\)
- \(f^{\omega}_1(f_2({\omega}))={\omega^3}\)
- \(f_2(f_2({\omega}))={\omega^{\omega}}\)
- \(f^{\omega}_1(f_2(f_2({\omega})))={\ome…
brainfωck
「brainfuckでn文字のコードでメモリ上に残すことができる最大の自然数」を\(BF(n)\)とする（メモリの個数も大きさも無限大とする）。brainfuckはチューリング完全（いかなる計算可能関数も表現できる）なので、\(BF(n)\)は計算不可能関数であり、\(f_(n)\)程度の強さである。
物置
- 1 関数の表記
- 2 構造公理
- 3 配列システム
- 4 角括弧演算子
- 4.1 概要
- 4.2 表記
- 4.3 計算法
- 4.4 評価
- 5 混合チェーン表記
- 5.1 概要
- 5.2 表記
- 5.3 計算法
- 5.3.1 例
- 5.4 評価
- 6 2-短成長階層
- 7 catching function
- 7.1 \(fH\)
- 7.2 \(fm\)
- 7.3 \(fg\)
- 7.4 \(gI\)
- 8 カードゲーム
計算方法で定義された巨大関数には「変数」「関数記号」「順序数」の3つで表記するものが多い。
そこで、それぞれに「N」「F」「O」という文字を当て、関数の表記を分類する。
- NFO型
例：超階乗配列表記、ドル関数、R関数
- FON型
例：FGH、SGH、ハーディー階層
- ON型
例：原始数列システム、バシク行列システム
- FNO型
例：ハイパーE表記
文字列をA型、B型、C型の3種類に分け、括弧（今回は角括弧に統一）による順序数表記の構造を公理のような形で定義する。
※あくまでも「よく使われる構造の例」であり、これらの組み合わせで表せないものもある。
- 空構造(E)
"\([]\)"はA型である
- 代入構造(S)
数\(n\)に対して"\([n]\)"はA型である
- 係数構造(C)
A型文字列\(a\)と数\(n\)に対して"\(an\)"はB型である
- 結合構造(U)
A型文字列\(a_1\)と\(a_2\)に対して\(a_1a_2\)はA型である
A型文字列\(a\)とB型文字列\(b\)に対して"\(ab\)"はB型である
- ネスト構造(N)
A型文字列とB型文字列はC型文字列でもある
A型文字列\(a\)に対して"\([a]\)"はA型である
- 配列構造(A)
数はC型である
C型文字列\(c_1\)と\(c_2\)に対して"\(c_1,c_2\)"はC型であ…