「「共終数がωである極限順序数」または「後続順序数」または「0」」かつ「λ以下の全ての順序数に対して基本列が定められている」順序数λと自然数を入力して自然数を出力する以下の関数\(f : λ\times N \rightarrow N \)は急増加関数と呼ばれている(リンク先の定義とはちょっと変えてる)。 \(\alpha\)を順序数、\(n\)を自然数、\(\alpha[n]\)を\(\alpha\)のn番目の基本列とする。
\begin{eqnarray} \left\{ \begin{array}{l} f_{0}(n) = n+1 \\ f_{\alpha +1}(n) = f_{\alpha}(f_{\alpha +1}(n-1)) = f_{\alpha}^{n}(n+1) \\ f_{\alpha}(n) = f_{\alpha[n]}(n) & (\alpha が極限順序数の場合) \end{array} \right. \end{eqnarray}
そして、アッカーマン関数の定義は以下の通り。 自然数を入力して自然数を出力する以下の関数\(A : N\times N \rightarrow N \)をアッカーマン関数とする(リンク先の定義とはちょっと変えてる)。 \(n,m\)を自然数とする。
\begin{eqnarray} \left\{ \begin{array}{l} A_{0}(n) = n+1 \\ A_{m}(0) = A_{m-1}(1) \\ A_{m+1}(n) = f_{m}(f_{m+1}(n-1)) = f_{m}^{n}(n+1) \end{array} \right. \end{eqnarray}
似てる！ この似てる様子を使って、アッカーマン急増加関数\(f : λ\times N \rightarrow N \)を定義してみる。 \(\alpha\)を順序数、\(n\)を自然数、\(\alpha[n]\)を\(\alpha\)の\(n\)番目の基本列とする。
\begin{eqnarray} \left\{ \begin{array}{l} f_{0}(n) = n+1 \\ f_{\alpha +1}(0) = f_{\alpha}(1) \\ f_{\alpha +1}(n) = f_{\alpha}(f_{\alpha +1}(n-1)) = f_{\alpha}^{n}(n+1) \\ f_{\alpha}(n) = f_{\alpha[n]}(n) & (\alpha が極限順序数の場合) \end{array} \right. \end{eqnarray}
このままだと急増加関数と変わらない印象なので、調子に乗って三変数アッカーマン急増加関数\(f : λ\times λ\times N \rightarrow N \)にしてみる。 \(\alpha , \beta \)を順序数、\(n\)を自然数、\(\alpha[n]\)を\(\alpha\)の\(n\)番目の基本列とする。
\begin{eqnarray} \left\{ \begin{array}{l} f_{0,0}(n) = n+1 \\ f_{\alpha , \beta +1}(0) = f_{\alpha , \beta}(1) \\ f_{\alpha , \beta +1}(n) = f_{\alpha , \beta}(f_{\alpha , \beta +1}(n-1)) = f_{\alpha , \beta}^{n}(n+1) \\ f_{\alpha +1 , 0}(n) = f_{\alpha, n}(n) \\ f_{\alpha , 0}(n) = f_{\alpha[n], n}(n) & (\alpha が極限順序数の場合) \\ f_{\alpha , \beta}(n) = f_{\alpha, \beta[n]}(n) & (\beta が極限順序数の場合) \end{array} \right. \end{eqnarray}
(大きく定義を変えました。変更前のものは履歴を参照のこと。)