目次 アッカーマン関数の拡張 多変数Ak 2重リストAk 多重リストAk (定義無し) Hardy Functionと順序数 HardyFunction 順序数生成関数 多変数 C0 2重リスト C0 多重リスト C0 (定義無し) C0 + Ω 多変数 C1 C1 + Ω (定義無し) C1 + Ω_n (定義無し) C2 (定義無し) 順序数を用いない定義 H[ε_0未満の順序数](n) (hydra game) H[多変数C0で生成する順序数](n) C++言語による表現 ルール C0(整数, 順序数, 順序数) の実装 多変数 C0 の実装 ■■■■アッカーマン関数の拡張■■■■ ●多変数Ak ○説明 n個の整数から1個の整数を作る多重帰納関数 F[ω^ω](n) 位の増大度の関数となる ○定義 □ : 0個以上の0 X : 0個以上の0以上の整数 a, b : 0以上の整数 Ak(□, a) = a+1 Ak(X, b+1, 0) = Ak(X, b, 1) Ak(X, b+1, a+1) = Ak( X, b, Ak(X, b+1, a) ) Ak(X, b+1, 0, □, a ) = Ak(X, b, a, □, a) ○大きさ Ak(n, n) ≒ F[ω](n) Ak(1, 0, n) ≒ F[ω](n) Ak(a, 0, n) ≒ F[ω・a](n) Ak(n, 0, n) ≒ F[ω^2](n) Ak(1, 0, 0, n) ≒ F[ω^2](n) Ak(a, 0, 0, n) ≒ F[ω^2・a](n) Ak(n, 0, 0, n) ≒ F[ω^3](n) Ak(1, 0, 0, 0, n) ≒ F[ω^3](n) Ak(a, 0, 0, 0, n) ≒ F[ω^3・a](n) Ak(n, 0, 0, 0, n) ≒ F[ω^4](n) Ak(..., a3, a2, a1, a0, n) ≒ F[... + ω^3・a3 + ω^2・a2 + ω・a1 + a0](n) Ak(n個の1) ≒ F[ω^ω](n) ●2重リストAk ○説明 『●多変数Ak』を2重リストに拡張する 多変数Akのn個目の引数がa であることを、[n, a] と表現するようにし、 [] の中を多変数化することで拡張する F[ω^ω^ω](n) 位の増大度の関数となる ○定義 □ : 0個以上の0 X : 0個以上の0以上の整数 Y, Y1, Y2 : 0個以上の0以上の整数リスト a, b, c : 0以上の整数 N : 十分大きな整数に対し、 index [..., b3, b2, b1, b0, a0] = ... + N^3・b3 + N^2・b2 + N・b1 + b0 とし、 Ak( ) の中のリストは index の大きい順に表記する。 また、index が同じとなるリストは Ak( ) 内に複数含まないとする。 Ak(X1, [X, 0], X2) = Ak(Y1, Y2) Ak(X1, [□, X], X2) = Ak(Y1, [X], Y2) Ak([a]) = a+1 Ak(Y, [1, b+1]) = Ak(Y, [1, b], [1]) Ak(Y, [1, b+1], [a+1]) = Ak( Y, [1, b], [Ak(Y, [1, b+1], [a])] ) Ak(Y, [X, c+1, b+1], [a]) = Ak(Y, [X, c+1, b], [X, c, a], [a]) ... X ≠ □ or c ≠ 0 Ak(Y, [X, c+1, 0, □, b+1], [a]) = Ak(Y, [X, c+1, 0, □, b], [X, c, a, □, a], [a]) ○大きさ Ak([n, 1], [n]) ≒ F[ω^ω](n) Ak([1, 0, 1], [n]) ≒ F[ω^ω](n) Ak([a, 0, 1], [n]) ≒ F[ω^(ω・a)](n) Ak([n, 0, 1], [n]) ≒ F[ω^ω^2](n) Ak([1, 0, 0, 1], [n]) ≒ F[ω^ω^2](n) Ak([a, 0, 0, 1], [n]) ≒ F[ω^(ω^2・a)](n) Ak([n, 0, 0, 1], [n]) ≒ F[ω^ω^3](n) Ak([1, 0, 0, 0, 1], [n]) ≒ F[ω^ω^3](n) Ak([1, 0, 0, 0, 0, 1], [n]) ≒ F[ω^ω^4](n) Ak([1, 0, 0, 0, 0, 0, 1], [n]) ≒ F[ω^ω^5](n) Ak(..., [3, a3], [2, a2], [1, a1], [0, a0]) = Ak(a3, a2, a1, a0) Ak([..., b3, b2, b1, b0, a], [n]) ≒ F[ω^(... + ω^3・b3 + ω^2・b2 + ω・b1 + b0)・a](n) Ak([n個の1], [n]) ≒ F[ω^ω^ω](n) ●多重リストAk ○説明 多変数Akから2重リストAkに拡張したのと同様の拡張を繰り返すことで、 多重リストが定義できる。 ○大きさ 3重リスト Ak([[1, 0, 1], [1]], [[n]]) ≒ F[ω^ω^ω](n) Ak([[1, 0, 0, 1], [1]], [[n]]) ≒ F[ω^ω^ω^2](n) Ak([[1, 0, 0, 0, 1], [1]], [[n]]) ≒ F[ω^ω^ω^3](n) Ak([..., [3, a3], [2, a2], [1, a1], [0, a0]], [[n]]) = Ak([..., a3, a2, a1, a1], [n]) Ak([[n個の1], [1]], [[n]]) ≒ F[ω^ω^ω^ω](n) 4重リスト Ak([[[1, 0, 1], [1]], [[1]]], [[[n]]]) ≒ F[ω^^4](n) Ak([[[1, 0, 0, 1], [1]], [[1]]], [[[n]]]) ≒ F[ω^ω^ω^ω^2](n) Ak([[[1, 0, 0, 0, 1], [1]], [[1]]], [[[n]]]) ≒ F[ω^ω^ω^ω^3](n) Ak([[..., [3, a3], [2, a2], [1, a1], [0, a0]]], [[[n]]]) = Ak([[..., a3, a2, a1, a1]], [[n]]) Ak([[[n個の1], [1]], [[1]]], [[[n]]]) ≒ F[ω^^5](n) n重リスト n重リストとすることで F[ε_0](n) に到達 ■■■■Hardy Function と順序数■■■■ ********Hardy Function******** ○説明 F[順序数](自然数), H[順序数](自然数) の形で、1個の自然数を表す。 定義の中に、順序数に収束する収束列が出てくるが、 この収束列は順序数に対して複数存在し、 この収束列の取り方によって値が変わる。 このため、厳密には[ ] の中の順序数を構成する全ての順序数に対して 収束列を定義してはじめて F[順序数] や H[順序数] が定義されたことになる。 つまり、厳密には、 F[順序数と、それを構成するすべての極限順序数それぞれの収束列](n) という形になる。 ただ、収束列のとり方による増大度の違いよりは順序数の大きさによる 増大度の方がはるかに大きい為、 F[順序数] や H[順序数] と記述し、大体の大きさを表す。 Hardy 関数と大きな順序数を用いることで増大度の大きい関数が作れ、 効率的に巨大な数が作れる。 ○定義 n : 0以上の整数 a : 順序数 A : 極限順序数 A_n がその収束列 (1) F[0](n) = n+1 F[a+1](n) = (F[a])^n (n) F[A](n) = F[A_n](n) (2) H[0](n) = n H[a+1](n) = H[a](n+1) H[A](n) = H[A_n](n) ○F と H の比較 F[a] ≒ H[ω^a] ※厳密には収束列のとり方に依存する。 ω^a = a となる順序数に対しては、 収束列のとり方による差程度の違いしかない。 ********順序数生成関数******** ●多変数 C0 ○説明 順序数から順序数への多変数関数 0 とこの関数だけで、ψ(Ω^ω) 未満のすべての順序数を作ることが出来る ○定義 □ : 0個以上の0 X : 0個以上の0以上の順序数 a, b : 順序数 B : 極限順序数 (B_n : 収束列) C0(□, a) = a+1 C0(X, b+1, a) = lim { 初項 a / 2項目以降 C0(X, b, 1個前の項) } C0(X, b+1, 0, □, a) = lim { 初項 0 / 2項目以降 C0(X, b, 1個前の項, □, a) } C0(X, B, □, a) = lim C0(X, B_n, □, a) ○大きさ C0(a, 0) = ω^a C0(1, 0, 0) = ε_0 C0(2, 0, 0) = η_0 C0(1, 0, 0, 0) = Γ_0 = ψ(0) C0(1, 0, a, 0) = Γ_(ω^a) C0(1, 1, 0, 0) = Γ_Γ_...Γ_0 = ψ(Ω) C0(1, a, 0, 0) = ψ(Ω・a) C0(2, 0, 0, 0) = ψ(Ω^2) C0(2, 1, 0, 0) = ψ(Ω^2+Ω) C0(2, 2, 0, 0) = ψ(Ω^2+Ω・2) C0(2, 2, 0, 0) = ψ(Ω^2+Ω・2) C0(2, a, 0, 0) = ψ(Ω^2+Ω・a) C0(3, 0, 0, 0) = ψ(Ω^2・2) C0(4, 0, 0, 0) = ψ(Ω^2・3) C0(ω, 0, 0, 0) = ψ(Ω^2・ω) C0(1, 0, 0, 0, 0) = ψ(Ω^3) C0(1, 0, 0, 0, 0, 0) = ψ(Ω^4) C0(1, 0, 0, 0, 0, 0, 0) = ψ(Ω^5) lim C0(1がn個) = ψ(Ω^ω) C0(a, 0, 0) = φ(a, 0) ●2重リスト C0 ○説明 多変数C0のn個目の引数がa であることを、[n, a] と表現するようにし、 nを順序数に拡張、さらに[ ] の中を多変数化することで拡張 0 とこの関数だけで、ψ(Ω^Ω^ω) 未満のすべての順序数を作ることが出来る ○定義 □ : 0個以上の0 X : 0個以上の順序数 Y1, Y2, Y : 0個以上の順序数リスト a, b : 順序数 B : 極限順序数 (B_n : 収束列) Ω : 十分大きな順序数に対し、 index [..., b3, b2, b1, b0, a0] = ... + Ω^3・b3 + Ω^2・b2 + Ω・b1 + b0 とし、 CO( ) の中のリストは index の大きい順に表記する。 また、index が同じとなるリストは CO( ) 内に複数含まないとする。 C0(Y1, [X, 0], Y2) = C0(Y1, Y2) C0(Y1, [□, X], Y2) = C0(Y1, [X], Y2) C0([a]) = a+1 C0(Y, [1, b+1], [a]) = lim { 初項 a / 2項目以降 C0(Y, [1, b], [1個前の項]) } C0(Y, [X, c+1, b+1], [a]) = lim { 初項 1 / 2項目以降 C0(Y, [X, c+1, b], [X, c, 1個前の項], [a]) } ... X ≠ □ or c ≠ 0 C0(Y, [X, c+1, □, 0, b+1], [a]) = lim { 初項 1 / 2項目以降 C0(Y, [X, c+1, □, 0, b], [X, c, 1個前の項, □, 1], [a]} C0(Y, [X, B], [a]) = lim C0(Y, [X, B_n], [a]) ... X ≠ □ C0(Y, [X, C, □, b+1], [a]) = lim C0(Y, [X, C, □, b], [X, C_n, □, 1], [a]) ○大きさ C0([1, 0, 1]) = ψ(Ω^Ω) C0([1, 0, 0, 1]) = ψ(Ω^Ω^2) C0([1, 0, 0, 0, 1]) = ψ(Ω^Ω^3) lim C0([1がn個]) = ψ(Ω^Ω^ω) C0([..., b3, b2, b1, b0, a]) = ψ( Ω^(... + Ω^3・b3 + Ω^2・b2 + Ω・b1 + b0)・a ) C0(..., [3, a3], [2, a2], [1, a1], [0, a0]) = C0(..., a3, a2, a1, a0) ●多重リスト C0 ○説明 多変数C0から2重リストC0に拡張したのと同様の拡張を繰り返すことで、 多重リストが定義できる。 ○大きさ 3重リスト φ([[1, 0, 1], [1]]) = ψ(Ω^Ω^Ω) φ([[1, 0, 0, 1], [1]]) = ψ(Ω^Ω^Ω^2) φ([[1, 0, 0, 0, 1], [1]]) = ψ(Ω^Ω^Ω^3) lim φ([[1がn個], [1]]) = ψ(Ω^Ω^Ω^ω) 4重リスト φ([[[1, 0, 1], [1]], [[1]]]) = ψ(Ω^Ω^Ω^Ω) φ([[[1, 0, 0, 1], [1]], [[1]]]) = ψ(Ω^Ω^Ω^Ω^2) φ([[[1, 0, 0, 0, 1], [1]], [[1]]]) = ψ(Ω^Ω^Ω^Ω^3) lim φ([[[1がn個], [1]], [[1]]]) = ψ(Ω^Ω^Ω^Ω^ω) n重リスト n重リストの極限をとることで、 ψ(ε_(Ω+1)) = Bachmann-Howard ordinal に到達 ●C0 + Ω ○説明 C0 に、帰納的独立な順序数Ωを加えることで、 Bachmann-Howard ordinal 未満の全ての順序数を表現可能になる Dmytro Taranovsky の順序数の A General Notation ○定義 □ : 0個以上の0 X : 0個以上の0以上の順序数 a, b : 順序数 B : 極限順序数 (B_n : 収束列) BB : 極限でも b+1の形でも 0 でも無い順序数 (BB.f(x) は BB に対応付けられた、順序数=>順序数 の関数) Ω : 帰納的独立な順序数 C0(0, a) = a+1 C0(b+1, a) = lim { 初項 a / 2項目以降 C0(b, 1個前の項) } C0(B, a) = lim C0(B_n, a) C0(BB, a) = lim { 初項 0 / 2項目以降 C0(BB.f(1個前の項), a) } ... a < Ω C0(BB, a).f(x) = C0(BB.f(x), a) ... a ≧ Ω Ω.f(x) = x ○大きさ C0(Ω, 0) = ε_0 C0(Ω・2, 0) = η_0 C0(Ω^2, 0) = Γ_0 = ψ(0) C0(Ω^2 + Ω, 0) = Γ_Γ_...Γ_0 = ψ(Ω) C0(Ω^2・2, 0) = ψ(Ω^2) C0(Ω^3, 0) = ψ(Ω^3) C0(Ω^4, 0) = ψ(Ω^4) C0(Ω^Ω, 0) = ψ(Ω^Ω) CO(ε_(Ω+1), 0) = ψ(ε_(Ω+1)) = Bachmann-Howard ordinal C0(Ω, Ω) = Ω+Ω C0(Ω+Ω, Ω) = Ω^2 C0(Ω^2, Ω) = Ω^Ω C0(Ω^Ω, Ω) = Ω^Ω^Ω C0(Ω^Ω^Ω, Ω) = Ω^Ω^Ω^Ω lim { 初項 Ω / 2項目以降 C0(1個前の項, Ω) } = ε_(Ω+1) C0(... + Ω^3・b3 + Ω^2・b2 + Ω・b1 + b0, a) = C0(..., b3, b2, b1, b0, a) C0( Ω^(... + Ω^3・b3 + Ω^2・b2 + Ω・b1 + b0)・a, 0 ) = C0([..., b3, b2, b1, b0, a]) ●多変数 C1 ○説明 Dmytro Taranovsky の順序数の An Ordinal Notation を多変数化したもの ψ では表現できない大きさの順序数まで作ることが出来る ○定義 C1(□, a) = a+1 C1(X, b+1, a) = lim { a / C(X, b, 前) } C1(X, b+1, □, 0, a) .f(x) = x deg a < [X, b+1, □] deg f = [X, b+1, □] C1(X, b+1, □, 0, a) = lim { 0 / C1(X, b, 前, □, a) } deg a ≧ [X, b+1, □] C1(X, B, □, a) = lim C1(X, B_n, □, a) C1(X, BB, □, a) .f(x) = C1(X, BB.f(x), □, a) deg BB.f ≦ deg C1(X, BB, □, a) deg f = deg BB.f C1(X, BB, □, a) = lim { 0 / C1(X, BB.f(前), □, a) } deg BB.f = deg C1(X, BB, □, a) + 1 C1(X, BB, □, a) = lim C1(X, S[n], □, a) } deg BB.f ≧ deg C1(X, BB, □, a) + 2 S[n] = { 0 / C1(Y, c, BB.f(前), ◇, 0) } deg BB.f = [Y, c+1, ◇] deg 0 = 0 deg C1(X, b, a) = max { [X], deg a } ○大きさ C1(1, 0, 0) = Ω とすると、C0 + Ω と 2変数限定C1 + C1(1, 0, 0) は同じになる C1( C1(1, 0, 0, 0), 0) = ψ(Ψ) ●C1 + Ω ○説明 Dmytro Taranovsky の順序数の A Stronger Ordinal Notation ○定義 (未完成) ●C1 + Ω_n ○説明 Dmytro Taranovsky の順序数の Second Order Arithmetic ○定義 (未完成) ●多変数 C2 ○説明 Dmytro Taranovsky の順序数の Beyond Second Order Arithmetic の多変数化 ○定義 (未完成) ********順序数を用いない定義******** ●H[ε_0未満の順序数](n) (hydra game) ○説明 0, ω^x, 加算を表現できるような文字列を順序数の代わりにすることで、 H[ε_0未満の順序数](n) を表現する。 空の文字列で0を表し、 (x) でω^x を表し、 文字列の単純な連結で加算を表す。 ○定義 N:非負整数 とする (0, 1, 2, .....) ■集合T ○定義 ( ) の2つの文字からなる文字列の集合で、以下の2つの条件を満たす最小のもの "" (空文字列)はTの元である Tの元を1個以上有限個繋げた物はTの元である Tの元に対し、( ) でくくった物はTの元である 演算子 + で文字列の連結を表す "(())" + "()" = "(())()" 文字列・自然数 で文字列の自然数個の連結を表す "()"・5 = "()()()()()" ○意味 葉が0の多進木 0 と和と1変数関数で生成する数 と対応する "(())" = func(func(0)) "((()())())" = func(func(func(0)+func(0))+func(0)) ■Seq : T×N => T ○定義 Seq は T×N から T への関数であり以下を満たす s = "" の時 Seq(s, i) は未定義 s = a + "()" の形の時 Seq(s, i) = a s = X + "(" + a + "(" + ")"・(n+2) の形の時 Seq(s, i) = X + { "(" + a + ")" }・(i+1) + ")"・n ただし、 s, a ∈ T X : ( ) からなる文字列 i ∈ N ■H[a] : N => N ○定義 a ∈ T とし、H[a] で N => N の関数を表し以下を満たす H[""](n) = n H[A](n) = H[Seq(A, n)](n+1) ただし、 A ∈ T, A ≠ 0 ○大きさ H["(((...(がn個...((( )))...)がn個...)))"](n) ≒ F[ε_0](n) ●H[多変数C0で生成する順序数](n) ○説明 0, 多変数C0 を表現できるような文字列を順序数の代わりにすることで、 H[多変数C0で生成する順序数](n) を表現する。 順序数 0 はそのまま"0"で表し、 ( ) で C0( ) を表す。 ○定義 N:非負整数 とする (0, 1, 2, .....) ■集合T ○定義 0 ( ) の3つの文字からなる文字列の集合で、以下の2つの条件を満たす最小のもの "0" はTの元である Tの元を1個以上有限個繋げて () でくくったものはTの元である 演算子 + で文字列の連結を表す "(0)" + "0" = "(0)0" ○意味 葉が0の多進木 0と多変数の関数funcで生成できる数 と対応する "(000)" => (0,0,0) => func(0, 0, 0) "((0)0(0)((0)0))" => ((0),0,(0),((0),0)) => func( func(0), 0, func(0), func( func(0), 0 ) ) ■Seq : T×N => T ○定義 Seq は T×N から T への関数であり以下を満たす s = "0" の時 Seq(s, i) は未定義 s = "(" + □ + a + ")" の形の時 Seq(s, i) = a s = "(" + X + B + □ + a + ")" の形の時 Seq(s, 0) = "(" + a + ")" Seq(s, i+1) = "(" + X + Seq(B, i+1) + Seq(s, i) + □ + ")" ただし、 s, a, b, B ∈ T ただし、B ≠ 0 □ : 0個以上の0を有限個繋げたもの X : 0個以上のTの元を有限個繋げたもの i ∈ N ■H[a] : N => N ○定義 a ∈ T とし、H[a] で N => N の関数を表し以下を満たす H[0](n) = n H[A](n) = H[Seq(A, n)](n+1) ただし、 A ∈ T, A ≠ 0 ○大きさ H[((0)0000...0がn個...0000)](n) ≒ F[ψ(Ω^ω)](n) ********C++言語による表現******** ●ルール 基本文法はC++言語 int 型はすべての整数値を保持できるとする メモリ使用量や実行速度は考えなくて良い プリプロセッサは無し ライブラリやインクルードファイルの使用は不可 以下のプロトタイプの main 関数が返す値の大きさを競う。 int main(); プログラムサイズはトークン(単語)数で数える。 ただし、例外として数値と文字列は1文字1トークンで数える。 処理系に依存する記述や不定な動作のプログラムは不可 ●C0(整数, 順序数, 順序数) の実装 // 3変数に限定した C0 で、一番上位の変数を整数に限定 // F[φ_ω(0)](9) = H[CO(9,0,0)](9) 程度の数を返す // 117 words // C0(c, b, a) struct ordinal { int c; ordinal *b, *a; ordinal* prev(int n){ ordinal t = {c, b ? b->prev(n) : 0, n ? prev(n-1) : a}; return b || t.c-- && (t.b = t.a) ? new ordinal(t) : a; } } a = {9}, *t = &a; int main(){ int n = 9; while (t = t->prev(++n)); return n; } ●多変数 C0 の実装 // 多変数 C0 // F[ψ(Ω^ω)](9) = H[C0(1,0,0,0,0,0,0,0,0)](9)程度の数を返す // 132 words // C0(p[0], p[1], ..., p[8]) struct ordinal { ordinal* p[9]; ordinal* prev(int n){ ordinal t = *this, **u = t.p + 8; while (n && (*u = prev(n-1)), u-- != t.p) if (*u) return *u = (*u)->prev(n), new ordinal(t); return p[8]; } } a, b = {&a}, *t = &b; int main(){ int n = 9; while (t = t->prev(++n)); return n; }