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

更新日時 2021/03/07

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

目次
  • ハイパー演算子とは

  • nn が小さい場合の具体例

  • クヌースの矢印表記

ハイパー演算子とは

nn を正の整数とします。

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

  • f1(a,b)=a+bf_1(a,b)=a+b

  • fn+1(a,b)f_{n+1}(a,b)bb 個の aafnf_n を順々にかましたもの

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

fn+1(a,1)=af_{n+1}(a,1)=a

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

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

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

という感じです。

nn が小さい場合の具体例

n=1n=1 は足し算

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

n=2n=2 はかけ算

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

n=3n=3 はべき乗

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

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

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

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

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

クヌースの矢印表記

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

f3(a,b)=abf_3(a,b)=a\uparrow b

f4(a,b)=abf_4(a,b)=a\uparrow\uparrow b

f5(a,b)=ab=a3bf_5(a,b)=a\uparrow\uparrow\uparrow b=a\uparrow^3 b

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

ハイパー演算子という名前はかっこいいですが,やはり何に使うのかは分かりません。