アッカーマン関数
配列表記では 1 が最小の数だが、多変数アッカーマンでは 0 が最小の数となっている。
数を並べる順番が左右逆になっている。配列表記では右の数の方が数を大きくする効果が大きく、多変数アッカーマンではその逆である。
配列表記では末尾が1になるとそれが消えるが、多変数アッカーマン関数では先頭が0になると実質的にそれが消える。
配列表記は {a,b} = a の 2 変数関数が基本となり、多変数アッカーマンは A(a) = a+1 の 1 変数関数(後者関数)が基本となっている。
配列表記では {a,b,1,...,1,c,d...,n} ={a,a,a,...,{a,b−1,1,...,1,c,d, ...,n},c−1,d,...,n}と、前の数が全部 a に変わる。多変数アッカーマンでは A(N,b+1,0,M,a) = A(N,b,a,M,a)と、1つ右の数だけ変わる。
特に最後の点がだいぶ違うように見えるが、多変数アッカーマン関数でも A(2,0,0,0,0,5) = A(1,5,0,0,0,5) = A(1,4,5,0,0,5) = A(1,4,4,5,0,5) = A(1,4,4,4,5,5) のように、結局は1つずつ数が変わっていくので、本質的にはそれほど変わらない。
また、多変数アッカーマン関数を更に拡張したものとして、「2重リストアッカーマン関数」や、「多重リストアッカーマン関数」といったものも考えられている。