Fandom

巨大数研究 Wiki

多重帰納関数

548このwikiの
ページ数
新しいページをつくる
コメント0 シェアする
多重帰納関数
基本関数 後者関数
急増加関数 \(f_{\omega^\omega}(n)\)

多重帰納関数 (Multiply recursive function) あるいは多重再帰関数とは、原始再帰関数(原始帰納関数)を拡張して、原始帰納ではない関数を含むような帰納関数一般をあらわすものとして、再帰理論では理解されている。たとえば、アッカーマン関数は原始再帰関数ではない帰納関数である。

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

  1. ゼロ関数 (zero function): \(f(x_1,…,x_n)=0\)
  2. 後者関数 (successor function): \(f(x)=x+1\)
  3. 射影関数 (projection function): 複数の引数を持つ関数から、i番目の引数を返す関数 \(f(x_1,…,x_n) = x_i\)
  4. 合成作用素 (composition operator): fとgの合成関数hは \[h(x_1,...,x_m) = f(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n))\]
  5. 原始帰納作用素 (primitive recursion operator): fとgの原始帰納関数 h は \[h(0,x_1,...,x_k) = f(x_1,...,x_k), \]

\[h(n+1,x_1,...,x_k) = g(h(n,x_1,...,x_k),n,x_1,...,x_k) \]


『巨大数論』[1]では、アッカーマン関数よりも大きい帰納関数の帰納程度を緻密に表現するために、n重帰納関数が次のように定義された。

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

このように定義することで、アッカーマン関数 \(A(x,y)\) は、x が定数の時には原始帰納作用素を x 回適用した原始帰納関数であるが、x が関数の引数の時には、原始帰納作用素を適用する回数が関数の引数となり、原始帰納作用素を数え上げる2重帰納作用素が適用された2重帰納関数となる。アッカーマン関数があらゆる原始帰納関数を支配するように[2]、n重帰納関数があらゆるn-1重帰納関数を支配すると予想されるが、厳密な証明はまだ与えられていない[3]

上記の定義にもとづき、いくつかの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)\) となる。多重帰納関数をμ再帰関数の意味で使えば、その範囲は計算可能関数全体にまで広がる。

出典 編集

  1. ふぃっしゅっしゅ (2013) 『巨大数論
  2. 藤田博司 (2012) 原始帰納的函数とアッカーマン函数
  3. User_blog:Mikadukim/2重帰納関数の評価 ~支配定理に向けて~

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWiki