巨大数研究 Wiki
登録
巨大数研究 Wiki
編集の要約なし
タグ: ソースの編集
(10人の利用者による、間の35版が非表示)
3行目: 3行目:
 
|base=ハイパー演算子
 
|base=ハイパー演算子
 
|fgh=\omega^2}}
 
|fgh=\omega^2}}
'''チェーン表記''' (chained arrow notation) は、[[wikipedia:ja:ジョン・ホートン・コンウェイ|コンウェイ]]イによる[[矢印表記]]の一般化である<ref>[https://docs.google.com/viewer?a=v&q=cache:gv7MebfOp6oJ:futuretg.com/FTHumanEvolutionCourse/FTFreeLearningKits/01-MA-Mathematics,%2520Economics%2520and%2520Preparation%2520for%2520University/011-MA11-UN03-10-Number%2520Theory%2520and%2520Cryptography/Additional%2520Resources/J.H.%2520Conway,%2520R.K.%2520Guy%2520-%2520The%2520Book%2520of%2520Numbers.pdf+The+Book+of+Numbers+by+J.+H.+Conway+and+R.+K.+Guy&hl=en&pid=bl&srcid=ADGEEShgWcsuShpVnS-hYtNfbwOq4TEpkeQ7YOZGVEk-omzaiEs4VKdsXFz1Su-Uh1po2QEXnmSivKhRixbQK6puTsf92WYUWuAcxyeOpXvn4JcEs-wsAJ1aF1Bk5I4JU7WCKoOUQCTL&sig=AHIEtbT5_BLlXtiF0i6dMiG6hNP8C58zKw ''The Book of Numbers'', by J. H. Conway and R. K. Guy]</ref><ref>[http://planetmath.org/encyclopedia/ConwaysChainedArrowNotation.html Chained Arrow Notation]</ref><ref>[[wikipedia:ja:コンウェイのチェーン表記|コンウェイのチェーン表記 (Wikipedia)]]</ref>。
+
'''チェーン表記''' (Chained arrow notation) は、{{wja|ジョン・ホートン・コンウェイ}}イによる[[矢印表記]]の一般化である<ref name="conway">[http://www.amazon.com/The-Book-Numbers-John-Conway/dp/038797993X Conway, John Horton. (1995) Book of Numbers] [https://docs.google.com/viewer?a=v&q=cache:gv7MebfOp6oJ:futuretg.com/FTHumanEvolutionCourse/FTFreeLearningKits/01-MA-Mathematics,%2520Economics%2520and%2520Preparation%2520for%2520University/011-MA11-UN03-10-Number%2520Theory%2520and%2520Cryptography/Additional%2520Resources/J.H.%2520Conway,%2520R.K.%2520Guy%2520-%2520The%2520Book%2520of%2520Numbers.pdf+The+Book+of+Numbers+by+J.+H.+Conway+and+R.+K.+Guy&hl=en&pid=bl&srcid=ADGEEShgWcsuShpVnS-hYtNfbwOq4TEpkeQ7YOZGVEk-omzaiEs4VKdsXFz1Su-Uh1po2QEXnmSivKhRixbQK6puTsf92WYUWuAcxyeOpXvn4JcEs-wsAJ1aF1Bk5I4JU7WCKoOUQCTL&sig=AHIEtbT5_BLlXtiF0i6dMiG6hNP8C58zKw PDF]</ref><ref>[http://www.amazon.co.jp/dp/4431707700/ J.H.コンウェイ、R.K.ガイ 『数の本』 根上生也訳、シュプリンガー・フェアラーク東京], 2001年12月</ref><ref>[http://planetmath.org/encyclopedia/ConwaysChainedArrowNotation.html Chained Arrow Notation]</ref><ref>[[wikipedia:ja:コンウェイのチェーン表記|コンウェイのチェーン表記 (Wikipedia)]]</ref>。
 
[[多変数アッカーマン関数]]はチェーン表記よりも大きい。また、[[バードの証明]]によれば、[[Jonathan Bowers]]の[[配列表記]]はチェーン表記よりも大きな値となる。
 
[[多変数アッカーマン関数]]はチェーン表記よりも大きい。また、[[バードの証明]]によれば、[[Jonathan Bowers]]の[[配列表記]]はチェーン表記よりも大きな値となる。
   
== ==
+
== 定義 ==
  +
以下の4つのルールで計算ができる。
   
\(a \rightarrow b \rightarrow c = a\underbrace{\uparrow\ldots\uparrow}_cb\) ([[矢印表記]]を使用)
+
'''ルール1''': \(a \rightarrow b \rightarrow c = a\underbrace{\uparrow\ldots\uparrow}_cb\) ([[矢印表記]]を使用)
   
最後の数字が1の時は、取り除くことができる。 \(a \rightarrow\ldots\rightarrow b \rightarrow 1 = a \rightarrow\ldots\rightarrow b\)
+
'''ルール2''': 最後の数字が1の時は、取り除くことができる。 \(a \rightarrow\ldots\rightarrow b \rightarrow 1 = a \rightarrow\ldots\rightarrow b\)
   
\(a \rightarrow\ldots\rightarrow b \rightarrow 1 \rightarrow c = a \rightarrow\ldots\rightarrow b\)
+
'''ルール3''': \(a \rightarrow\ldots\rightarrow b \rightarrow 1 \rightarrow c = a \rightarrow\ldots\rightarrow b\)
   
\(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'''': \(a \rightarrow b = a^b\)
   
 
== CG 関数 ==
 
== CG 関数 ==
   
コンウェイとイは、チェーン表記を使って \(cg(n) = \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n\). という関数を定義した。
+
コンウェイとイは、チェーン表記を使って \(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) に相当する。
   
 
== Peter Hurford の拡張 ==
 
== Peter Hurford の拡張 ==
   
Peter Hurford は、チェーン表記に次のルールを加えることで拡張した<ref>{{cite web|first=Peter|last=Hurford|url=http://www.greatplay.net/essays/large-numbers-part-ii-graham-and-conway|title=Large Numbers, Part 2: Graham and Conway|accessdate=2013-04-02}}</ref>。
+
Peter Hurford は、チェーン表記に次のルールを加えることで拡張した'''拡張チェーン表記'''を考案した<ref>{{cite web|first=Peter|last=Hurford|url=http://www.greatplay.net/essays/large-numbers-part-ii-graham-and-conway|title=Large Numbers, Part 2: Graham and Conway|archiveurl=https://archive.today/rEzX6|archivedate=2013-06-25|deadurl=yes|accessdate=2015-03-28}}</ref>。
   
\(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 = \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)\) 程度であることを示した<ref>{{cite web|first=Peter|last=Hurford|url=http://www.greatplay.net/essays/large-numbers-part-3-functions-and-ordinals|title=Large Numbers, Part 3: Functions and Ordinals|accessdate=2013-04-02}}</ref>。
より正確にはこのようになる。
 
 
\(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)\) 程度であることを示した<ref>{{cite web|first=Peter|last=Hurford|url=http://www.greatplay.net/essays/large-numbers-part-3-functions-and-ordinals|title=Large Numbers, Part 3: Functions and Ordinals|accessdate=2013-04-02}}</ref>。
 
   
 
さらに、彼は C(n) 関数を次のように定義した。
 
さらに、彼は C(n) 関数を次のように定義した。
52行目: 51行目:
 
\(C(a,b,c) = C(a,C(a,b-1,c),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)\) 程度の増加速度となる。
+
\(f(n) = C(n,n,n)\) 関数は、急増加関数で \(f_{\omega^3 + \omega}(n)\) 程度の増加速度となる。
   
 
== プログラム ==
 
== プログラム ==
チェーン表記の計算を実行するプログラムが書かれている<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 \)
  +
  +
\(3 \rightarrow 2 \rightarrow 3 = 3^{3^3} = 3^{27} = 7625597484987 \)
  +
  +
\(4 \rightarrow 3 \rightarrow 2 = 4^{4^4} = 4^{256} = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 \)
  +
  +
  +
== 近似 ==
  +
コンウェイは[[グラハム数]] が 3&rarr;3&rarr;64&rarr;2 と 3&rarr;3&rarr;65&rarr;2 の間の大きさであり、したがって 3&rarr;3&rarr;3&rarr;3 よりも小さいとした<ref name="conway" />。そのことは、次のように確かめられる<ref>フィッシュ (2017) [https://gyafun.jp/ln/ 巨大数論 第2版] p.79</ref>。g(x) = 3↑<sup>x</sup>3 = 3&rarr;3&rarr;x とすると グラハム数 = g<sup>64</sup>(4) であり、
  +
  +
* 3&rarr;3&rarr;1&rarr;2 = 3&rarr;3&rarr;1 = g(1) = 27
  +
* 3&rarr;3&rarr;2&rarr;2 = 3&rarr;3&rarr;(3&rarr;3&rarr;1&rarr;2)&rarr;1 = 3&rarr;3&rarr;(3&rarr;3&rarr;1) = g(g(1)) = g<sup>2</sup>(1) = 3&rarr;3&rarr;27 = g(27)
  +
* 3&rarr;3&rarr;3&rarr;2 = 3&rarr;3&rarr;(3&rarr;3&rarr;2&rarr;2) = g<sup>3</sup>(1) = g<sup>2</sup>(27)
  +
* 3&rarr;3&rarr;n&rarr;2 = g<sup>n</sup>(1) = g<sup>n-1</sup>(27)
  +
* 3&rarr;3&rarr;64&rarr;2 = g<sup>64</sup>(1) < g<sup>64</sup>(4) = グラハム数
  +
* 3&rarr;3&rarr;65&rarr;2 = g<sup>64</sup>(27) > g<sup>64</sup>(4) = グラハム数
  +
* 3&rarr;3&rarr;3&rarr;3 = 3&rarr;3&rarr;(3&rarr;3&rarr;2&rarr;3)&rarr;2 > 3&rarr;3&rarr;65&rarr;2 > グラハム数
  +
  +
この近似を使うと、[[モーザー数]] \(\approx g(10\uparrow\uparrow257) < g(g(3))\) であるため、このようになる。
  +
  +
* 3&rarr;3&rarr;2&rarr;2 < モーザー数 < 3&rarr;3&rarr;3&rarr;2
  +
  +
[[多変数アッカーマン関数]]との間には次の関係がある<ref>[http://gyafun.jp/ln/ackchain.html アッカーマンチェーン定理]</ref>。
  +
  +
\(x=1, y>1\) または \(x>1, y+z>0\) のとき
  +
  +
\[A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1個の3} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)\]
  +
  +
ワイナー階層を基本列とする順序数による[[急増加関数]]では、次のように近似できる。
  +
  +
*\(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)\)
  +
  +
== 動画 ==
 
*[http://www.nicovideo.jp/mylist/35451262 巨大数動画シリーズ] (ニコニコ動画) より
  +
 
1. 出典: [http://www.nicovideo.jp/watch/sm22403264 チェーン表記・Ⅰ]
  +
 
2. 出典: [http://www.nicovideo.jp/watch/sm22844479 チェーン表記・II]
  +
  +
3. 出典: [http://www.nicovideo.jp/watch/sm25432965 チェーン表記・III]
  +
  +
*[http://www.nicovideo.jp/mylist/59089039 ゆっくり巨大数講座] (ニコニコ動画) より
   
 
== 出典 ==
 
== 出典 ==
 
<references />
 
<references />
 
== 外部リンク ==
 
*[http://www.nicovideo.jp/mylist/35451262 巨大数動画シリーズ] (ニコニコ動画)
 
**[http://www.nicovideo.jp/watch/sm22403264 チェーン表記・Ⅰ]
 
**[http://www.nicovideo.jp/watch/sm22844479 チェーン表記・II]
 
   
 
== 関連項目 ==
 
== 関連項目 ==
74行目: 170行目:
   
 
[[en:Chained arrow notation]]
 
[[en:Chained arrow notation]]
[[カテゴリ:法]]
+
[[zh:鏈式箭號表示法]]
  +
[[カテゴリ:動画あり]]
  +
[[カテゴリ:多重再帰関数]]
  +
[[カテゴリ:表記]]

2021年7月3日 (土) 11:00時点における版

チェーン表記
多次元
基本関数 ハイパー演算子
急増加関数 \(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→3→64→2 と 3→3→65→2 の間の大きさであり、したがって 3→3→3→3 よりも小さいとした[1]。そのことは、次のように確かめられる[10]。g(x) = 3↑x3 = 3→3→x とすると グラハム数 = g64(4) であり、

  • 3→3→1→2 = 3→3→1 = g(1) = 27
  • 3→3→2→2 = 3→3→(3→3→1→2)→1 = 3→3→(3→3→1) = g(g(1)) = g2(1) = 3→3→27 = g(27)
  • 3→3→3→2 = 3→3→(3→3→2→2) = g3(1) = g2(27)
  • 3→3→n→2 = gn(1) = gn-1(27)
  • 3→3→64→2 = g64(1) < g64(4) = グラハム数
  • 3→3→65→2 = g64(27) > g64(4) = グラハム数
  • 3→3→3→3 = 3→3→(3→3→2→3)→2 > 3→3→65→2 > グラハム数

この近似を使うと、モーザー数 \(\approx g(10\uparrow\uparrow257) < g(g(3))\) であるため、このようになる。

  • 3→3→2→2 < モーザー数 < 3→3→3→2

多変数アッカーマン関数との間には次の関係がある[11]

\(x=1, y>1\) または \(x>1, y+z>0\) のとき

\[A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1個の3} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)\]

ワイナー階層を基本列とする順序数による急増加関数では、次のように近似できる。

  • \(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

出典

関連項目