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

$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=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\geqq 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$

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

計算例

計算例をいくつか確認しましょう。

• $5 \uparrow 3 = 5^3 = 125$
• $2 \uparrow \uparrow 3 = 2^{(2^2)} = 2^4 = 16$

計算の注意

複数の矢印があるときは右から計算します。つまり

$$\begin{aligned} 2\uparrow 3 \uparrow 2 &= 2 \uparrow 3^2\\ &= 2 \uparrow 9\\ &= 2^9\\ &= 512 \end{aligned}$$ と計算します。

ハイパー演算子を用いて定義される巨大な数としてグラハム数があります。

グラハム数は，数学の証明で使われたことのある最大の数としてギネスブックに掲載されています。

グラハム数に関する定理を紹介します。