二重再帰の増加速度

アッカーマン関数に代表される二重再帰関数は原始再帰的でない全域的再帰関数の例として有名ですが、その証明においては「任意の原始再帰関数よりアッカーマン関数の方が速く増加する」ということを証明することで、アッカーマン関数が原始再帰関数で表現できないことを示します。

ここから、二重再帰および多重再帰の考え方が生まれ、巨大数論の中でも一つのステップを形成するほど大きなトピックを構成するわけですが、実際二重再帰の繰り返しはどの程度の増加を示すのでしょうか？

さしあたり、二重再帰関数をn重に数え上げる関数の大きさはÂ(n,m)=A(A(..A(A(m,1),1)...,1),1)と同程度でしかないことをざっくりと示します。
厳密な定式化はしてないので細かいところで訂正が必要かもしれませんが、少なくともこれに関して直接的な対角化は関数の増加にあまり寄与しないことを示します。

--${\displaystyle }$

アッカーマン関数$A(m,n)$を以下で定義します。 $\begin{cases} A(0,n) &= n+1 \\ A(m+1,0) &= A(m,1) \\ A(m+1,n+1) &= A(m,A(m+1,n)) \\ \end{cases}$

この時、以下の性質が成り立ちます。

• $A(m,n) < A(m,n+1)$
• $n < A(m,n)$
• $A(m,n) < A(m+1,n)$
• $m+1 < A(m,1)$

$n < A(m,n)$から、任意の$m$に対して$A(m,n)$は無限大まで増大することが分かります。
また、$m+1 < A(m,1)$から、任意の$n$に対しても$A(m,n)$は無限大まで増大することがわかります。

いま、自然数上の関数$f: \mathbb{N} \rightarrow \mathbb {N}$について、$M=\max(m,f(n))$とおくと$A(m,f(n)) < A(M+1,1)$が成り立ちます。

ここから、二重再帰関数を数え上げる関数（二重再帰関数に対して原始再帰を行ったもの）の増加速度は、ざっくりと
$\hat{A}(n,m)=_{def}\begin{cases} m, &\mathrm{if\ }n=0 \\ A(\hat{A}(n-1,m),m), &\mathrm{if\ }n\geq1 \\ \end{cases}$ で見積もれば十分ということがわかります。

次回：ユーザーブログ:Merliborn/二重再帰 (2)→

${\displaystyle }$--