アッカーマン関数
多変数関数 A ( a , b , . . . , y , z ) {\displaystyle A(a,b,...,y,z)} を以下のように定義する。
A ( M , a ) = a + 1 {\displaystyle A(M,a)=a+1}
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)}
A ( N , b + 1 , 0 ) = A ( N , b , 1 ) {\displaystyle A(N,b+1,0)=A(N,b,1)}
A ( N , b + 1 , a + 1 ) = A ( N , b , A ( N , b + 1 , a ) ) {\displaystyle A(N,b+1,a+1)=A(N,b,A(N,b+1,a))}
( a , b : {\displaystyle a,b:} 0 {\displaystyle 0} 以上の任意の整数, M : {\displaystyle M:} 0 {\displaystyle 0} 個以上の 0 {\displaystyle 0} , N : {\displaystyle N:} 0 {\displaystyle 0} 個以上の 0 {\displaystyle 0} 以上の整数)
{ n , 2 , b + 1 , c + 1 , d + 1 , e + 1 , ⋯ } ≒ A ( ⋯ , e , d , c , b , n ) {\displaystyle \{n,2,b+1,c+1,d+1,e+1,\cdots \}\fallingdotseq A(\cdots ,e,d,c,b,n)}
次に、配列表記の2変数目が3以上の場合は、
{ n , a , b + 1 , c + 1 , d + 1 , e + 1 , ⋯ } ≒ A ( ⋯ , e , d , c , b , A ( ⋯ , e , d , c , b , ⋯ , A ( ⋯ , e , d , c , b , n ) ⋯ ) ) {\displaystyle \{n,a,b+1,c+1,d+1,e+1,\cdots \}\fallingdotseq A(\cdots ,e,d,c,b,A(\cdots ,e,d,c,b,\cdots ,A(\cdots ,e,d,c,b,n)\cdots ))} (括弧はa-1重)
ただし、配列表記では先頭が1ならその値は1に、4変数以上で先頭が2ならば、2変数目が1であれば2、2変数目が1でなければ4になってしまうし、更に配列表記では0も要素として使えないので、多変数アッカーマン関数においてnが2以下の場合はこの近似式は直接適用できない。
配列表記と多変数アッカーマン関数を比較すると、両者には次のような違いがあるが、最終的な振る舞いや特徴は似ている。