アッカーマン関数
アッカーマンが1928年に発表した3変数の関数は次のような定義である:
φ ( a , b , 0 ) = a + b φ ( a , 0 , n + 1 ) = { n ( if n = 0 , 1 ) a ( otherwise ) φ ( a , b + 1 , n + 1 ) = φ ( a , φ ( a , b , n + 1 ) , n ) {\displaystyle {\begin{aligned}\varphi (a,b,0)&=a+b\\\varphi (a,0,n+1)&={\begin{cases}n&({\textrm {if}}\ n=0,1)\\a&({\textrm {otherwise}})\\\end{cases}}\\\varphi (a,b+1,n+1)&=\varphi (a,\varphi (a,b,n+1),n)\end{aligned}}}
この関数において、 φ ( a , b , n + 1 ) {\displaystyle \varphi (a,b,n+1)} は φ ( a , _ , n ) {\displaystyle \varphi (a,\_,n)} を b 回繰り返すことによって定義されていることがわかる。
この関数は、本質的には通常のアッカーマン関数に: A ( N , b + 1 , 0 , M , a ) = A ( N , b , a , M , a ) {\displaystyle A(N,b+1,0,M,a)=A(N,b,a,M,a)} のルールが追加されただけで、あとの3行は通常のアッカーマン関数の前に飾りが付いただけのものである。
この関数は n {\displaystyle n} 変数関数 ( A ( x , 0 , 0 , . . . , 0 , x ⏟ n ) ) {\displaystyle (A(\underbrace {x,0,0,...,0,x} _{n}))} が急増加関数で f ω n − 1 ( x ) {\displaystyle f_{\omega ^{n-1}}(x)} 程度の強さとなる。これは配列表記(非拡張)と同じくらいの強さであり、3変数でコンウェイのチェーン表記レベル、4変数でピーター・ハーフォードによる拡張チェーン表記(あるいは回転矢印表記)レベルの巨大数となり、5変数以上になるとそのレベルを超える。
配列表記と多変数アッカーマン関数の間には近似関係があり、次のような式で表される。まず、配列表記の2変数目が2の場合は、