2016/05/05

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

分野: 式の計算  レベル: マニアック

足し算,かけ算,べき乗を一般化したハイパー演算というものがある。

ハイパー演算子とは

$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$
という感じです。これをクヌースの矢印表記と言います。

ハイパー演算子という名前はかっこいいですが,やはり何に使うのかは分かりません。
分野: 式の計算  レベル: マニアック