巨大数研究 Wiki
登録
巨大数研究 Wiki
17行目: 17行目:
 
'''ルール4''': \(a \rightarrow\ldots\rightarrow b \rightarrow (c + 1) \rightarrow (d + 1) = a \rightarrow\ldots\rightarrow b \rightarrow (a \rightarrow\ldots\rightarrow b \rightarrow c \rightarrow (d + 1) ) \rightarrow d\)
 
'''ルール4''': \(a \rightarrow\ldots\rightarrow b \rightarrow (c + 1) \rightarrow (d + 1) = a \rightarrow\ldots\rightarrow b \rightarrow (a \rightarrow\ldots\rightarrow b \rightarrow c \rightarrow (d + 1) ) \rightarrow d\)
   
なお、ルール1を以下のルール1'に変えても同じである<ref>[User_blog:Kyodaisuu/チェーンと矢印表記の関係]</ref>。
+
なお、ルール1を以下のルール1'に変えても同じである<ref>[[User_blog:Kyodaisuu/チェーンと矢印表記の関係|チェーンと矢印表記の関係]]</ref>。
   
 
'''ルール1'''': \(a \rightarrow b = a^b\)
 
'''ルール1'''': \(a \rightarrow b = a^b\)

2014年3月6日 (木) 23:25時点における版

チェーン表記
多次元
基本関数 ハイパー演算子
急増加関数 \(f_{\omega^2}(n)\)

チェーン表記 (Chained arrow notation) は、ジョン・ホートン・コンウェイとガイによる矢印表記の一般化である[1][2][3][4]多変数アッカーマン関数はチェーン表記よりも大きい。また、バードの証明によれば、Jonathan Bowers配列表記はチェーン表記よりも大きな値となる。

定義

以下の4つのルールで計算ができる。

ルール1: \(a \rightarrow b \rightarrow c = a\underbrace{\uparrow\ldots\uparrow}_cb\) (矢印表記を使用)

ルール2: 最後の数字が1の時は、取り除くことができる。 \(a \rightarrow\ldots\rightarrow b \rightarrow 1 = a \rightarrow\ldots\rightarrow b\)

ルール3: \(a \rightarrow\ldots\rightarrow b \rightarrow 1 \rightarrow c = a \rightarrow\ldots\rightarrow b\)

ルール4: \(a \rightarrow\ldots\rightarrow b \rightarrow (c + 1) \rightarrow (d + 1) = a \rightarrow\ldots\rightarrow b \rightarrow (a \rightarrow\ldots\rightarrow b \rightarrow c \rightarrow (d + 1) ) \rightarrow d\)

なお、ルール1を以下のルール1'に変えても同じである[5]

ルール1': \(a \rightarrow b = a^b\)

CG 関数

コンウェイとグイは、チェーン表記を使って \(cg(n) = \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n\). という関数を定義した。

この関数の増加率は、急成長階層で \(f_{\omega^2}(n)\) であり、多変数アッカーマン関数では A(1,0,0,n) に相当する。

Peter Hurford の拡張

Peter Hurford は、チェーン表記に次のルールを加えることで拡張した拡張チェーン表記を考案した[6]

\(a \rightarrow_c b = \underbrace{a \rightarrow_{c-1} a \rightarrow_{c-1}\ldots\rightarrow_{c-1} a \rightarrow_{c-1}a}_{b \rightarrow_{c-1}'s}\)

より正確にはこのようになる。

\(a \rightarrow_c b = a \rightarrow_{c-1} (a \rightarrow_c (b-1))\)

\(a \rightarrow_c 1 = a \rightarrow_{c-1} a\)

他のチェーンの規則は、そのままであり、→の下についている数字を無視して計算できる。したがって、 \(3 \rightarrow_{2} 3 \rightarrow 3\) のような表記はできない。つまり、矢印のタイプ(→の下についている数字)は、1通りでなければならない。さらに、Hurford は \(f(n) = n \rightarrow_n n\) が急成長階層で \(f_{\omega^3}(n)\) 程度であることを示した[7]

さらに、彼は C(n) 関数を次のように定義した。

\(C(a) = a \rightarrow_a a\)

\(C(a,1) = a \rightarrow_{C(a)} a\)

\(C(a,b) = a \rightarrow_{C(a,b-1)} a\)

\(C(a,1,1) = C(a,C(a,a))\)

\(C(a,b,1) = C(a,C(a,b-1,1))\)

\(C(a,1,c) = C(a,C(a,a,c-1),c-1)\)

\(C(a,b,c) = C(a,C(a,b-1,c),c-1)\)

\(f(n) = C(n,n,n)\) 関数は、急成長階層で \(f_{\omega^3 + \omega}(n)\) 程度の増加速度となる。

プログラム

チェーン表記の計算を実行するプログラムが書かれている[8][9]

動画 

1. 出典: チェーン表記・Ⅰ

<nicovideo>sm22403264</nicovideo>

2. 出典: チェーン表記・II

<nicovideo>sm22844479</nicovideo>

出典

関連項目