コンウェイのチェーン表記
[Wikipedia|▼Menu]

コンウェイのチェーン表記(コンウェイのチェーンひょうき、: Conway chained arrow notation)とは、1995年イギリス数学者ジョン・ホートン・コンウェイによって導入された巨大数の表記法の一つである。

クヌースの矢印表記アッカーマン関数などより比較的強い演算である。具体的には、3つ組ではクヌースの矢印表記と等価だが、更に長く続けることで、クヌースの矢印表記では簡潔に表せない、あるいは現実的に表せない大きな数を表すことができる。
導入

加法を反復すると乗法、乗法を反復すると累乗が得られる。このとき累乗を上向き矢印によって a ↑ b = ab と表して、さらに ↑ の反復を ↑↑(テトレーション)、↑↑ の反復を ↑↑↑(ペンテーション)、というように矢印を増やしていくことで累乗の先の演算を表せるようにしたものをクヌースの矢印表記と呼ぶ。 ( 1 ) a × b = a + a + ⋯ + a ⏟ b  copies of  a = a + ⋯ a + ⏟ b − 1   a ( 2 ) a ↑ b = a × a × ⋯ × a ⏟ b  copies of  a = a × ⋯ a × ⏟ b − 1   a ( 3 ) a ↑ c b = a ↑ c − 1 a ↑ c − 1 ⋯ ↑ c − 1 a ⏟ b  copies of  a = a ↑ c − 1 ⋯ a ↑ c − 1 ⏟ b − 1   a = a   ↑ c − 1 a ⋯ ↑ c − 1 a ⏟ b − 1  copies of  a {\displaystyle {\begin{array}{lclcl}(1)\qquad a\times b&=&\underbrace {a+a+\cdots +a} _{b{\text{ copies of }}a}&=&\underbrace {a+\cdots a\,+} _{b-1}~a\\(2)\qquad a\uparrow b&=&\underbrace {a\times a\times \cdots \times a} _{b{\text{ copies of }}a}&=&\underbrace {a\times \cdots a\,\times } _{b-1}~a\\(3)\qquad a\uparrow ^{c}b&=&\underbrace {a\uparrow ^{c-1}a\uparrow ^{c-1}\cdots \uparrow ^{c-1}a} _{b{\text{ copies of }}a}&=&\underbrace {a\uparrow ^{c-1}\cdots a\uparrow ^{c-1}} _{b-1}~a&=&a~\underbrace {\uparrow ^{c-1}a\cdots \uparrow ^{c-1}a} _{b-1{\text{ copies of }}a}\end{array}}\,\!}

コンウェイのチェーン表記は、このクヌースの矢印表記の一般化、拡張である。以下チェーンの各項はすべて自然数であるものとする。

コンウェイはまず長さが 3 のチェーンを、クヌースの矢印表記を用いて次のように与えた[1]。 ( 4 ) a → b → c = a ↑ ⋯ ↑ ⏟ c 本 b = a ↑ c b {\displaystyle (4)\qquad a\rightarrow b\rightarrow c=a\underbrace {\uparrow \cdots \uparrow } _{c{\text{本}}}b=a\uparrow ^{c}b} ( a → b = a b {\displaystyle a\rightarrow b=a^{b}} とも書き換えられる)

このチェーンによって (3) を書き換えると次のような式になる。これは末尾 → c のチェーンを末尾 → (c − 1) のチェーンに分解する式となっている。 ( 5 ) a → b → c = a ↑ c − 1 a ↑ c − 1 ⋯ a ↑ c − 1 a ↑ c − 1 a ↑ c − 1 a ⏟ b  copies of  a = a ↑ c − 1 a ↑ c − 1 a ↑ c − 1 ⋯ a ↑ c − 1 a ↑ c − 1 a ↑ c − 1 a ⏟ b − 1  copies of  a = a ↑ c − 1 a ↑ c ( b − 1 ) = a ↑ c − 1 { a → ( b − 1 ) → c } = a → { a → ( b − 1 ) → c } → ( c − 1 ) = a → ( a → ( ⋯ → ( a → ( a ⏟ b ) → ( c − 1 ) ) → ⋯ ) → ( c − 1 ) ) → ( c − 1 ) ⏟ b − 1 {\displaystyle (5)\qquad {\begin{aligned}a\rightarrow b\rightarrow c=&\underbrace {a\uparrow ^{c-1}a\uparrow ^{c-1}\cdots a\uparrow ^{c-1}a\uparrow ^{c-1}a\uparrow ^{c-1}a} _{b{\text{ copies of }}a}=a\uparrow ^{c-1}\underbrace {a\uparrow ^{c-1}a\uparrow ^{c-1}\cdots a\uparrow ^{c-1}a\uparrow ^{c-1}a\uparrow ^{c-1}a} _{b-1{\text{ copies of }}a}=a\uparrow ^{c-1}a\uparrow ^{c}\left(b-1\right)=a\uparrow ^{c-1}\left\{a\rightarrow \left(b-1\right)\rightarrow c\right\}\\=&a\rightarrow \left\{a\rightarrow (b-1)\rightarrow c\right\}\rightarrow (c-1)=\underbrace {a\rightarrow {\biggl (}a\rightarrow {\biggl (}\cdots \rightarrow {\Bigl (}a\rightarrow (\quad a} _{b}\quad \underbrace {)\rightarrow (c-1){\Bigr )}\rightarrow \cdots {\biggr )}\rightarrow (c-1){\biggr )}\rightarrow (c-1)} _{b-1}\end{aligned}}}


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:104 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef