多重再帰関数

多重再帰関数
基本関数	後者関数
急増加関数	\(f_{\omega^\omega}(n)\)

多重再帰関数 (Multiply recursive function) あるいは多重帰納関数とは、『巨大数論』において、原始再帰関数（原始帰納関数）を拡張して、原始再帰ではない関数を含むような再帰的関数一般をあらわすものとして導入された概念である。たとえば、アッカーマン関数は原始再帰関数ではない再帰的関数である。

原始再帰関数は以下の3つの関数と2つの作用素を有限回適用して得られる関数である。

1. ゼロ関数 (zero function): \(f(x_1,\ldots,x_n)=0\)
2. 後者関数 (successor function): \(f(x)=x+1\)
3. 射影関数 (projection function): 複数の引数を持つ関数から、i番目の引数を返す関数 \(f(x_1,\ldots,x_n) = x_i\)
4. 合成作用素 (composition operator): 以下のように定まる \(f(y_1,\ldots,y_k)\) と \(g_1(x_1,\ldots,x_n),\ldots,g_k(x_1,\ldots,x_n)\)の合成関数 \(h(x_1,\ldots,x_n)\)
   \[h(x_1,\ldots,x_n) = f(g_1(x_1,\ldots,x_n),\ldots,g_k(x_1,\ldots,x_n))\]
5. 原始再帰作用素 (primitive recursion operator): 以下のように定まる \(f(x_1,\ldots,x_k)\) と \(g(z,n,x_1,\ldots,x_k)\) の原始再帰 \(h(n,x_1,\ldots,x_k)\)
   

\begin{eqnarray*} h(0,x_1,\ldots,x_k) & = & f(x_1,\ldots,x_k), \\ h(n+1,x_1,\ldots,x_k) & = & g(h(n,x_1,\ldots,x_k),n,x_1,\ldots,x_k) \end{eqnarray*}

『巨大数論』では、アッカーマン関数よりも大きい再帰的関数の再帰の複雑さを緻密に表現するために、n重再帰関数が次のように定義された（第一版ではn重帰納関数と書かれていたが第二版から帰納 (induction) と再帰 (recursion) を分けるためn重再帰関数という言葉が用いられている）。

1. 2重再帰作用素とは、合成作用素を数え上げるような原始再帰作用素を数え上げる作用素である。すなわち、原始再帰作用素を適用する回数が関数の引数となっている作用素である。
2. 3以上の自然数nに対し、n-1重再帰作用素を数え上げる作用素をn重再帰作用素とする。
3. 2以上の自然数nに対し、n重再帰関数とは、定義域と値域が非負整数である非負整数個の引数をとる関数で、引数に対し、ゼロ、後者、射影、合成、原始再帰、2重再帰、3重、...、n重再帰の作用素を有限回適用した関数である。ただし、その中でn重再帰作用素を少なくとも1回含むものとする。

このように定義することで、アッカーマン関数 \(A(x,y)\) は、x が定数の時には原始再帰作用素を x 回適用した原始再帰関数であるが、x が関数の引数の時には、原始再帰作用素を適用する回数が関数の引数となり、原始再帰作用素を数え上げる2重再帰作用素が適用された2重再帰関数となる。

アッカーマン関数があらゆる原始再帰関数を支配するように、3以上の自然数nに対しn重再帰関数があらゆるn-1重再帰関数を支配するとふぃっしゅっしゅにより予想された。しかしみかづきもによりその予想を正当化するためには定義の修正が必要であることが指摘された。実際、関数 \(g \colon (x,y) \mapsto g_x(y)\) に2重再帰作用素を適用して得られる関数 \((x,y) \mapsto g_x^y(1)\) を \(C(g)\) と表し、原始再帰関数である射影 \( (x,y) \mapsto x \) を \(p_0\) と置くと、構成から確かに \(C(p_0)\) は2重再帰作用素 \(C\) を原始再帰関数 \(p_0\) に1回適用しているので2重再帰関数であり、 \begin{eqnarray*} C(p_0)(x,y) = \left\{ \begin{array}{ll} 1 & (y = 0) \\ x & (y > 0) \end{array} \right. \end{eqnarray*} より \(C(p_0)\) は原始再帰的関数でもある。特に2重再帰関数 \(C(p_0)\) は原始再帰的関数 \(C(p_0)+1\) を支配しない。同様に、3重再帰関数も2重再帰関数を必ずしも支配しない。

上記の定義にもとづき、いくつかのn重再帰作用素の例を挙げる。

作用素	急増加関数	s(n)変換	多変数アッカーマン関数
原始再帰作用素	\(f_{\alpha+1}(n) = f^n_\alpha(n)\)	\(s(1)f =f^x(x) \)	\(A(X, b+1, a+1) \\= A( X, b, A(X, b+1, a) ) \\ \text{すなわち} f(n) = A(X, b, n) \text{とすると} \\ A(X, b+1, n) \approx f^n(n)\)
2重再帰作用素	\(f_{\alpha+\omega}(n) = f_{\alpha+n}(n)\)	\(s(2)f(x) = s(1)^{x}f(x)\)	\(A(X, b+1, 0, a ) = A(X, b, a, a)\)
3重再帰作用素	\(f_{\alpha+\omega^2}(n) = f_{\alpha+\omega \times n}(n)\)	\(s(3)f(x) = s(2)^{x}f(x)\)	\(A(X, b+1, 0, 0, a ) = A(X, b, a, 0, a)\)
4重再帰作用素	\(f_{\alpha+\omega^3}(n) = f_{\alpha+\omega^2 \times n}(n)\)	\(s(4)f(x) = s(3)^{x}f(x)\)	\(A(X, b+1, 0, 0, 0, a ) = A(X, b, a, 0, 0, a)\)
n重再帰作用素	\(f_{\alpha+\omega^{n-1}}(n) = f_{\alpha+\omega^{n-2} \times n}(n)\)	\(s(n)f(x) = s(n-1)^{x}f(x)\)	\(A(X, b+1, n-1 個の 0, a ) \\ = A(X, b, a, n-2 個の 0, a)\)

3重再帰作用素が2重再帰作用素を数え上げているとは、次のようなことを意味している。

• 作用素 \(f_{\alpha+\omega^2}(n) = f_{\alpha+\omega \times n}(n)\) は、\(f_{\alpha}(n)\) に \(f_{\alpha+\omega}(n)\) という2重再帰作用素を、関数の引数であるところの n 回適用する作用素であるから、2重再帰作用素を数え上げる3重再帰作用素である。
• 作用素 \(s(3)\) は、関数 f(x) に対して、2重再帰作用素 \(s(2)\) を、関数の引数であるところの x 回適用する作用素であるから、2重再帰作用素を数え上げる3重再帰作用素である。
• \(A(X, b+1, 0, 0, a )\) の計算は、右から4番目の引数 b+1 を 1 減ずるために、右から3番目の引数にaを加えている。右から3番目の引数をa減ずるためには、右から3番目の引数を1減ずる2重再帰作用素をa回適用する必要があるため、2重再帰作用素を数え上げる3重再帰作用素である。

このような定義によれば、n重再帰関数とは、急増加関数で \(f_{\alpha}(n) (\omega^{n-1} \le \alpha < \omega^n)\) と近似される関数となる。したがって、その上限は \(f_{\omega^\omega}(n)\) となる。多重再帰関数をμ再帰関数の意味で使えば、その範囲は計算可能関数全体にまで広がる。