ハイパー演算子とクヌースの矢印

ハイパー演算子とは

$n$ を正の整数とします。

二つの正の整数 $a,b$ を受け取って一つの値を返す関数（ハイパー演算子）$f_n(a,b)$ を次のように定義します。

• $f_1(a,b)=a+b$

• $f_{n+1}(a,b)$ は $b$ 個の $a$ に $f_n$ を順々にかましたもの

二行目の定義は厳密ではありませんが，例えば

$f_{n+1}(a,1)=a$

$f_{n+1}(a,2)=f_n(a,a)$

$f_{n+1}(a,3)=f_n(a,f_n(a,a))$

$f_{n+1}(a,4)=f_n(a,f_n(a,f_n(a,a)))$

という感じです。

$n$ が小さい場合の具体例

$n=1$ は足し算

$f_1(a,b)$ は $a+b$ を返します。つまり $n=1$ の場合のハイパー演算は足し算です。

$n=2$ はかけ算

$f_2(a,2)=a+a=2a$ ，$f_2(a,3)=3a$ ，などの例からも分かるように，$f_2(a,b)=ab$ となります。つまり $n=2$ の場合のハイパー演算はかけ算です。

$n=3$ はべき乗

$f_3(a,2)=a\times a=a^2$ ，$f_3(a,3)=a^3$ ，などの例からも分かるように，$f_3(a,b)=a^b$ となります。つまり $n=3$ の場合のハイパー演算はべき乗です。

$n=4$ はテトレーション

$f_4(a,b)$ は馴染みがない演算です。 $f_4(a,2)=a^a$ ，$f_4(a,3)=a^{a^a}$ という感じです。 $n=4$ の場合のハイパー演算をテトレーションと言います。

ちなみに階乗，二重階乗，超階乗で紹介した超階乗は $f_4(n!,n!)$ と書くことができます。

$n$ が $5$ 以上の場合はイメージすることさえ難しいです。

クヌースの矢印表記

$n\geq 3$ に対して，$f_n(a,b)$ のことを $a$ と $b$ の間に上向き矢印を $(n-2)$ 本並べて表記することがあります。

$f_3(a,b)=a\uparrow b$

$f_4(a,b)=a\uparrow\uparrow b$

$f_5(a,b)=a\uparrow\uparrow\uparrow b=a\uparrow^3 b$

という感じです。これをクヌースの矢印表記と言います。