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

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

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

計算例

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

• $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}$$ と計算します。

$g(x) = 3 \uparrow^x 3$ と定義します。

$g^2$ を $g(g(x))$ と定め，同様に $g^n (x)$ を $g$ を $n$ 回適用した関数とします。

グラハム数を $g^{64} (4)$ と定義します。

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

グラハム数に関する定理として，次の定理が存在します。

この $n$ の1つの解としてグラハム数が紹介されました。