クヌースの上向き矢印表記法

数学において、クヌースの上向き矢印記法は、ドナルド・クヌースが1976年に導入した非常に大きな整数を表す記法である。 ^{[ 1 ]}

1947年の論文^{[ 2 ]}で、 RL Goodsteinは現在ハイパー演算と呼ばれる特定の演算シーケンスを導入しました。Goodsteinはまた、べき乗を超える拡張演算に対して、ギリシャ語のtetation、pentationなどの名称を提案しました。このシーケンスは単項演算（n = 0の後継関数）から始まり、加算（n = 1）、乗算（n = 2） 、べき乗（n = 3）、tetation（n = 4）など の二項演算へと続きます。ハイパー演算を表すために様々な表記法が用いられてきました。その1つが${\displaystyle H_{n}(a,b)}$クヌースの上向き矢印表記${\displaystyle \uparrow }$もう一つの例はこれです。例えば：

• 一本の矢${\displaystyle \uparrow }$べき乗（反復乗算）を表す$${\displaystyle 2\uparrow 4=H_{3}(2,4)=2\times (2\times (2\times 2))=2^{4}=16}$$
• 二重矢印${\displaystyle \uparrow \uparrow }$テトレーション（反復べき乗）を表す$${\displaystyle 2\uparrow \uparrow 4=H_{4}(2,4)=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^{2}}}=2^{16}=65,536}$$
• トリプルアロー${\displaystyle \uparrow \uparrow \uparrow }$ペンテーション（反復テトラレーション）を表す$${\displaystyle {\begin{aligned}2\uparrow \uparrow \uparrow 4&=H_{5}(2,4)\\&=2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow 2))\\&=2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow 2))\\&=2\uparrow \uparrow (2\uparrow \uparrow 4)\\&=\underbrace {2\uparrow (2\uparrow (2\uparrow \cdots ))} \;=\;\underbrace {\;2^{2^{\cdots ^{2}}}} \\&\;\;\;\;\;2\uparrow \uparrow 4{\text{ copies of }}2\;\;\;\;\;{\text{65,536 2's}}\\\end{aligned}}}$$

上向き矢印表記の一般的な定義は次のとおりです（${\displaystyle a\geq 0,n\geq 1,b\geq 0}$): $${\displaystyle a\uparrow ^{n}b=H_{n+2}(a,b)=a[n+2]b.}$$ ここ、${\displaystyle \uparrow ^{n}}$n個の矢印を表すので、例えば $${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3=2\uparrow ^{4}3,}$$ また、右辺の式で使用されている角括弧は、超演算を表す別の表記法です。

ハイパー演算は、加算と乗算の算術演算を以下のように自然に拡張します。

自然数による加算は、反復的な増分として定義される。

${\displaystyle {\begin{matrix}H_{1}(a,b)=a+b=&a+\underbrace {1+1+\dots +1} \\&b{\mbox{ copies of }}1\end{matrix}}}$

自然数による乗算は、反復加算として定義される。

${\displaystyle {\begin{matrix}H_{2}(a,b)=a\times b=&\underbrace {a+a+\dots +a} \\&b{\mbox{ copies of }}a\end{matrix}}}$

例えば、

${\displaystyle {\begin{matrix}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3{\mbox{ copies of }}4\end{matrix}}}$

自然数のべき乗${\displaystyle b}$これは反復乗算として定義され、クヌースはこれを単一の上向き矢印で表した。

${\displaystyle {\begin{matrix}a\uparrow b=H_{3}(a,b)=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ copies of }}a\end{matrix}}}$

例えば、

${\displaystyle {\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3{\mbox{ copies of }}4\end{matrix}}}$

テトレーションは反復べき乗として定義され、クヌースはこれを「二重矢印」で表した。

${\displaystyle {\begin{matrix}a\uparrow \uparrow b=H_{4}(a,b)=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\cdots \uparrow a))} \\&b{\mbox{ copies of }}a&&b{\mbox{ copies of }}a\end{matrix}}}$

例えば、

${\displaystyle {\begin{matrix}4\uparrow \uparrow 3=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}&&\\&3{\mbox{ copies of }}4&&3{\mbox{ copies of }}4\end{matrix}}}$

演算子は右結合性を持つように定義されているため、式は右から左に評価されます。

この定義によれば、

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}}$

等

これは既にかなり大きな数値につながりますが、ハイパー演算子のシーケンスはここで終わりません。反復テトラションとして定義されるペンテーションは、「三重矢印」で表されます。

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=H_{5}(a,b)=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\cdots \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

反復ペンタテーションとして定義されるヘキセーションは、「四重矢印」で表されます。

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=H_{6}(a,b)=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\cdots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

などなど。一般的なルールは、${\displaystyle n}$-矢印演算子は右結合の系列に展開されます (${\displaystyle n-1}$)-矢印演算子。記号的には、

${\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\cdots \!\!\uparrow } _{n}\ b=\underbrace {a\ \underbrace {\uparrow \!\!\cdots \!\!\uparrow } _{n-1}\ (a\ \underbrace {\uparrow _{}\!\!\cdots \!\!\uparrow } _{n-1}\ (\cdots \ \underbrace {\uparrow _{}\!\!\cdots \!\!\uparrow } _{n-1}\ a))} _{b{\text{ copies of }}a}\end{matrix}}}$

例：

${\displaystyle 3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

${\displaystyle {\begin{aligned}3\uparrow \uparrow \uparrow 3&=3\uparrow \uparrow (3\uparrow \uparrow 3)\\&=3\uparrow \uparrow (3\uparrow 3\uparrow 3)\\&={\begin{matrix}\underbrace {3\uparrow 3\uparrow \cdots \uparrow 3} \\3\uparrow 3\uparrow 3{\mbox{ copies of }}3\end{matrix}}\\&={\begin{matrix}\underbrace {3\uparrow 3\uparrow \cdots \uparrow 3} \\{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}\\&={\begin{matrix}\underbrace {3^{3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}}}} \\{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}\end{aligned}}}$

次のような表現では${\displaystyle a^{b}}$指数表記は通常、指数を${\displaystyle b}$基数の上付き文字として${\displaystyle a}$しかし、プログラミング言語やプレーンテキストの電子メールなど、多くの環境では上付き文字の組版がサポートされていません。人々は線形表記を採用しています。${\displaystyle a\uparrow b}$このような環境では、上向き矢印は「累乗」を意味します。文字セットに上向き矢印がない場合は、代わりにキャレット（^）が使用されます。

上付き文字表記${\displaystyle a^{b}}$一般化には向いていないため、クヌースがインライン記法を採用した理由が説明できる。${\displaystyle a\uparrow b}$その代わり。

${\displaystyle a\uparrow ^{n}b}$は n 個の上向き矢印を表すより短い代替表記です。したがって${\displaystyle a\uparrow ^{4}b=a\uparrow \uparrow \uparrow \uparrow b}$。

数値が大きすぎると、クヌースの上向き矢印表記の矢印が複数あっても煩雑になりすぎることがあります。その場合は、n 個の矢印演算子を使用します。 ${\displaystyle \uparrow ^{n}}$は（可変数の矢印を持つ記述にも）役立ちます。あるいは同等に、ハイパー演算子です。

数値があまりにも大きい場合、その表記法では不十分なことがあります。そのような場合は、コンウェイ連鎖矢印表記法を使用できます。3つの要素からなる連鎖は他の表記法と同等ですが、4つ以上の要素からなる連鎖はさらに強力です。

${\displaystyle {\begin{matrix}a\uparrow ^{n}b&=&a[n+2]b&=&a\to b\to n\\{\text{(Knuth)}}&&{\text{(hyperoperation)}}&&{\text{(Conway)}}\end{matrix}}}$

${\displaystyle 6\uparrow \uparrow 4=\underbrace {6^{6^{.^{.^{.^{6}}}}}} _{4}}$、 以来${\displaystyle 6\uparrow \uparrow 4=6^{6^{6^{6}}}=6^{6^{46,656}}}$したがって、結果は次のようになります。${\displaystyle \underbrace {6^{6^{.^{.^{.^{6}}}}}} _{4}}$

${\displaystyle 10\uparrow (3\times 10\uparrow (3\times 10\uparrow 15)+3)=\underbrace {100000\ldots 000} _{\underbrace {300000\ldots 003} _{\underbrace {300000\ldots 000} _{15}}}}$または${\displaystyle 10^{3\times 10^{3\times 10^{15}}+3}}$

さらに成長の速い関数も、高速成長階層と呼ばれる順序分析を用いて分類することができる。高速成長階層は、連続的な関数反復と対角化を用いて、ある基本関数からより高速に成長する関数を体系的に作成する。${\displaystyle f(x)}$標準的な急成長階層を使用する場合${\displaystyle f_{0}(x)=x+1}$、${\displaystyle f_{2}(x)}$すでに指数関数的な成長を示しており、${\displaystyle f_{3}(x)}$これは四元数成長に匹敵し、最初の４つの超演算子を含む関数によって上限が定められる。そして、${\displaystyle f_{\omega }(x)}$アッカーマン関数に匹敵する、${\displaystyle f_{\omega +1}(x)}$はすでにインデックス付き矢印の範囲を超えていますが、グラハムの数を近似するために使用できます。${\displaystyle f_{\omega ^{2}}(x)}$これは、任意に長いコンウェイ連鎖矢印表記に匹敵する。

これらの関数はすべて計算可能です。グッドスタイン数列やツリー数列など、さらに高速に計算可能な関数は、大きな順序数を使用する必要があり、特定の組み合わせ論や証明論の文脈で現れることがあります。一方、ビジービーバーのように、計算不可能なほど高速に増大する関数も存在し、その性質上、いかなる上向き矢印や、順序数に基づく解析でも完全に捉えることができません。

ハイパー演算を参照せずに、上向き矢印演算子は形式的に次のように定義できます。

${\displaystyle a\uparrow ^{n}b={\begin{cases}a^{b},&{\text{if }}n=1;\\1,&{\text{if }}n>1{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

すべての整数に対して${\displaystyle a,b,n}$と${\displaystyle a\geq 0,n\geq 1,b\geq 0}$[^{注1 ]}

この定義では指数法を使用しています${\displaystyle (a\uparrow ^{1}b=a\uparrow b=a^{b})}$基本ケースとして、そしてテトラレーション${\displaystyle (a\uparrow ^{2}b=a\uparrow \uparrow b)}$繰り返しべき乗演算として。これは、加算、加算、乗算というより基本的な 3 つの演算を省略した点を除けば、ハイパー演算シーケンスと同等です。

代わりに乗算を選択することもできます${\displaystyle (a\uparrow ^{0}b=a\times b)}$を基本ケースとして、そこから反復します。すると、べき乗は繰り返し乗算になります。正式な定義は次のようになります。

${\displaystyle a\uparrow ^{n}b={\begin{cases}a\times b,&{\text{if }}n=0;\\1,&{\text{if }}n>0{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

すべての整数に対して${\displaystyle a,b,n}$と${\displaystyle a\geq 0,n\geq 0,b\geq 0}$。

ただし、クヌースは「nil矢印」を定義していないことに注意してください（${\displaystyle \uparrow ^{0}}$) 表記法を負のインデックス (n ≥ -2) に拡張すれば、インデックス付けの遅延を除いて、ハイパー演算シーケンス全体と一致するようにできる。

${\displaystyle H_{n}(a,b)=a[n]b=a\uparrow ^{n-2}b{\text{ for }}n\geq 0.}$

上向き矢印の操作は右結合操作です。つまり、${\displaystyle a\uparrow b\uparrow c}$理解されているのは${\displaystyle a\uparrow (b\uparrow c)}$、 の代わりに${\displaystyle (a\uparrow b)\uparrow c}$曖昧さが問題にならない場合は、括弧が省略されることがあります。

• 原始的な再帰
• カトラーのバー記法
• シュタインハウス・モーザー記法

• Weisstein, Eric W. 「Knuth上向き矢印表記法」 . MathWorld .
• ロバート・ムナフォ著『大きな数：より高度なハイパー演算子』