(計算例を追記した。) タグ: ビジュアルエディタ apiedit |
細編集の要約なし |
||
(6人の利用者による、間の6版が非表示) | |||
23行目: | 23行目: | ||
== CG 関数 == |
== CG 関数 == |
||
− | コンウェイと |
+ | コンウェイとガイは、チェーン表記を使って \(cg(n) = \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n\). という関数を定義した。 |
この関数の増加率は、[[急増加関数]]で \(f_{\omega^2}(n)\) であり、[[多変数アッカーマン関数]]では A(1,0,0,n) に相当する。 |
この関数の増加率は、[[急増加関数]]で \(f_{\omega^2}(n)\) であり、[[多変数アッカーマン関数]]では A(1,0,0,n) に相当する。 |
||
54行目: | 54行目: | ||
== プログラム == |
== プログラム == |
||
− | チェーン表記の計算を実行するプログラムが書かれている<ref>[http://cflat-inc.hatenablog.com/entry/2013/11/11/214650 全宇宙の素粒子の数を超えて…C++で巨大数に挑戦!] (株式会社CFlatの明後日スタイルのブログ)</ref><ref>[https://github.com/aycabta/chained-arrow-notation]</ref>。 |
+ | チェーン表記の計算を実行するプログラムが書かれている<ref>[http://cflat-inc.hatenablog.com/entry/2013/11/11/214650 全宇宙の素粒子の数を超えて…C++で巨大数に挑戦!] (株式会社CFlatの明後日スタイルのブログ)</ref><ref>aycabta, [https://github.com/aycabta/chained-arrow-notation chained arrow notation], github.</ref>。 |
== 計算例 == |
== 計算例 == |
||
− | \(2 \rightarrow 3 \rightarrow 3 = 2^{2^{2^2}} = 2^16 = 65536 \) |
+ | \(2 \rightarrow 3 \rightarrow 3 = 2^{2^{2^2}} = 2^{16} = 65536 \) |
− | \(3 \rightarrow 2 \rightarrow 3 = 3^{3^3} = 3^27 = 7625597484987 \) |
+ | \(3 \rightarrow 2 \rightarrow 3 = 3^{3^3} = 3^{27} = 7625597484987 \) |
− | \(4 \rightarrow 3 \rightarrow 2 = 4^{4^4} = 4^256 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 \) |
+ | \(4 \rightarrow 3 \rightarrow 2 = 4^{4^4} = 4^{256} = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 \) |
+ | |||
+ | |||
+ | == 急増加関数との比較 == |
||
+ | *\(3 \rightarrow 3 \rightarrow n \sim f_\omega (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \sim f_\omega (27) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \sim f^2_\omega (27) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2) \sim f^3_\omega (27) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega +1} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 2 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \rightarrow 2 \sim f_{\omega +1} (26) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 3) \rightarrow 2 \sim f^2_{\omega +1} (26) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 4 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 3) \rightarrow 2 \sim f^3_{\omega +1} (26) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega +2} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 2 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \rightarrow 3 \sim f_{\omega +2} (26) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 4) \rightarrow 3 \sim f^2_{\omega +2} (26) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 4 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 4) \rightarrow 3 \sim f^3_{\omega +2} (26) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega +3} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 5 \sim f_{\omega +4} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 6 \sim f_{\omega +5} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 2} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3) \sim f_{\omega \times 2} (f_4 (3)) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \sim f^2_{\omega \times 2} (f_4 (3)) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 2) \sim f^3_{\omega \times 2} (f_4 (3)) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega \times 2 +1} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega \times 2 +2} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega \times 2 +3} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 3} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega \times 3 +1} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega \times 3 +2} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega \times 3 +3} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 4} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 5} (n) \) |
||
+ | |||
+ | *\(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 6} (n) \) |
||
+ | |||
+ | *\(\underbrace{3 \rightarrow 3 \rightarrow \ldots \rightarrow 3 \rightarrow 3}_{n+2} \sim f_{\omega^2}(n)\) |
||
== 動画 == |
== 動画 == |
||
67行目: | 129行目: | ||
1. 出典: [http://www.nicovideo.jp/watch/sm22403264 チェーン表記・Ⅰ] |
1. 出典: [http://www.nicovideo.jp/watch/sm22403264 チェーン表記・Ⅰ] |
||
− | |||
− | <nicovideo>sm22403264</nicovideo> |
||
2. 出典: [http://www.nicovideo.jp/watch/sm22844479 チェーン表記・II] |
2. 出典: [http://www.nicovideo.jp/watch/sm22844479 チェーン表記・II] |
||
− | |||
− | <nicovideo>sm22844479</nicovideo> |
||
3. 出典: [http://www.nicovideo.jp/watch/sm25432965 チェーン表記・III] |
3. 出典: [http://www.nicovideo.jp/watch/sm25432965 チェーン表記・III] |
||
+ | *[http://www.nicovideo.jp/mylist/59089039 ゆっくり巨大数講座] (ニコニコ動画) より |
||
− | <nicovideo>sm25432965</nicovideo> |
||
== 出典 == |
== 出典 == |
||
91行目: | 149行目: | ||
[[en:Chained arrow notation]] |
[[en:Chained arrow notation]] |
||
[[zh:鏈式箭號表示法]] |
[[zh:鏈式箭號表示法]] |
||
⚫ | |||
[[カテゴリ:動画あり]] |
[[カテゴリ:動画あり]] |
||
− | [[カテゴリ:多重帰 |
+ | [[カテゴリ:多重再帰関数]] |
⚫ |
2020年10月29日 (木) 06:05時点における版
チェーン表記 | |
---|---|
型 | 多次元 |
基本関数 | ハイパー演算子 |
急増加関数 | \(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}}\)
他のチェーンの規則は、そのままであり、→の下についている数字を無視して計算できる。したがって、 \(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]。
計算例
\(2 \rightarrow 3 \rightarrow 3 = 2^{2^{2^2}} = 2^{16} = 65536 \)
\(3 \rightarrow 2 \rightarrow 3 = 3^{3^3} = 3^{27} = 7625597484987 \)
\(4 \rightarrow 3 \rightarrow 2 = 4^{4^4} = 4^{256} = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 \)
急増加関数との比較
- \(3 \rightarrow 3 \rightarrow n \sim f_\omega (n) \)
- \(3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \sim f_\omega (27) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \sim f^2_\omega (27) \)
- \(3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2) \sim f^3_\omega (27) \)
- \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega +1} (n) \)
- \(3 \rightarrow 3 \rightarrow 2 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \rightarrow 2 \sim f_{\omega +1} (26) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 3) \rightarrow 2 \sim f^2_{\omega +1} (26) \)
- \(3 \rightarrow 3 \rightarrow 4 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 3) \rightarrow 2 \sim f^3_{\omega +1} (26) \)
- \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega +2} (n) \)
- \(3 \rightarrow 3 \rightarrow 2 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \rightarrow 3 \sim f_{\omega +2} (26) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 4) \rightarrow 3 \sim f^2_{\omega +2} (26) \)
- \(3 \rightarrow 3 \rightarrow 4 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 4) \rightarrow 3 \sim f^3_{\omega +2} (26) \)
- \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega +3} (n) \)
- \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 5 \sim f_{\omega +4} (n) \)
- \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 6 \sim f_{\omega +5} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 2} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3) \sim f_{\omega \times 2} (f_4 (3)) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \sim f^2_{\omega \times 2} (f_4 (3)) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 2) \sim f^3_{\omega \times 2} (f_4 (3)) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega \times 2 +1} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega \times 2 +2} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega \times 2 +3} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 3} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega \times 3 +1} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega \times 3 +2} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega \times 3 +3} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 4} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 5} (n) \)
- \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 6} (n) \)
- \(\underbrace{3 \rightarrow 3 \rightarrow \ldots \rightarrow 3 \rightarrow 3}_{n+2} \sim f_{\omega^2}(n)\)
動画
- 巨大数動画シリーズ (ニコニコ動画) より
1. 出典: チェーン表記・Ⅰ
2. 出典: チェーン表記・II
3. 出典: チェーン表記・III
- ゆっくり巨大数講座 (ニコニコ動画) より
出典
- ↑ Conway, John Horton. (1995) Book of Numbers PDF
- ↑ J.H.コンウェイ、R.K.ガイ 『数の本』 根上生也訳、シュプリンガー・フェアラーク東京, 2001年12月
- ↑ Chained Arrow Notation
- ↑ コンウェイのチェーン表記 (Wikipedia)
- ↑ チェーンと矢印表記の関係
- ↑ Hurford, Peter. Large Numbers, Part 2: Graham and Conway. Retrieved 2015-03-28.
- ↑ Hurford, Peter. Large Numbers, Part 3: Functions and Ordinals. Retrieved 2013-04-02.
- ↑ 全宇宙の素粒子の数を超えて…C++で巨大数に挑戦! (株式会社CFlatの明後日スタイルのブログ)
- ↑ aycabta, chained arrow notation, github.