μ再帰関数

μ再帰関数︵ミューさいきかんすう、英: μ-recursive function︶または帰納的関数︵きのうてきかんすう︶とは、数理論理学と計算機科学において、直観的に﹁計算可能﹂な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数︵原始帰納的関数︶と密接な関連があり、その帰納的定義︵後述︶は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。

また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。

計算複雑性理論では、全再帰関数の集合をRと称する。

定義

μ再帰関数︵または部分μ再帰関数︶は、有限個の自然数の引数をとり、1つの自然数を返す部分関数である。μ再帰関数は初期関数を含み、合成や原始再帰やμ作用素において閉じている、部分関数の最小のクラスである。

原始再帰関数も同じような形式で定義されるが、全域関数という点が異なる。また、原始再帰関数は、3つの基本関数︵定数関数、後者関数、射影関数︶と2つの作用素︵合成と原始再帰︶で定義されるが、μ再帰関数にはさらにμ作用素が登場する。これはアッカーマン関数のように原始再帰関数でない全域再帰関数を定義するためである。μ再帰関数においてμ作用素は計算を終了させる。μ作用素は無制限探索演算子として働き、︵全域関数の定義から︶無制限ではあるが何らかの手段︵帰納的定義など︶で最終的に数を生成し計算を終わらせるのである。

しかし、無制限μ作用素自身が部分的な場合︵つまり、ある数について数を返せないことがある場合︶、それを使って定義された関数も部分関数となり、一部の数については値が定義されない。この場合、無制限という性質上、μ作用素は永遠に探索を続け、計算を終了して数を返すことがない。アルゴリズムによっては、"u" という記号で ﹁決定不能︵undecided︶﹂を表し、計算を終了させるとする場合もある︵例えば、Kleene (1952) pp. 328ff︶。換言すれば、部分μ再帰関数は部分μ作用素を使うため、全域的でない可能性がある。全域μ再帰関数︵total μ-recursive functions︶は部分μ再帰関数の部分集合である。

以下の定義は Kleene (1952) p. 219 に基づいている。最初の3つの関数(1)-(3)を﹁初期関数︵initial functions︶﹂または﹁基本関数︵basic functions)﹂と呼ぶ。その他の記号体系については﹁記号体系﹂の節を参照されたい。

●(1) 定数関数︵Constant function︶: 任意の自然数 $n$$n$と $k$$k$について:

$f(x_{1},\ldots ,x_{k})=n$$f(x_{1},\ldots ,x_{k})=n$.
定数 $n$$n$は、﹁初期オブジェクト・ゼロ︵initial object 0︶﹂と呼ばれるオブジェクトに後者関数を繰り返し適用することで生成されることがある。

●(2) 後者関数︵Successor function︶S: 既に生成されたオブジェクトから別のオブジェクト $n+1$$n+1$または $n'$$n'$︵$n$$n$ の後者︶への逐次的経路

${\displaystyle S($x){\stackrel {\mathrm {def} }{=}}f(x)=x'=x+1\,} $S(x){\stackrel {\mathrm {def} }{=}}f(x)=x'=x+1\,$
●(3) 射影関数︵Projection function︶P_i^k ︵Identity function I_i^k とも︶: $1\leq i\leq k$$1\leq i\leq k$であるような全ての自然数 $i$$i$について:

$P_{i}^{k}{\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=x_{i}$$P_{i}^{k}{\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=x_{i}$.

●(4) 合成作用素︵Composition operator︶: 置換︵substitution︶とも呼ばれ、関数 $h(x_{1},\ldots ,x_{m})$$h(x_{1},\ldots ,x_{m})$と $1\leq i\leq m$$1\leq i\leq m$であるような $i$$i$それぞれについての関数 $g_{i}(x_{1},\ldots ,x_{k})$$g_{i}(x_{1},\ldots ,x_{k})$をとり、$x_{1},\ldots ,x_{k}$$x_{1},\ldots ,x_{k}$ を以下のようにマップする関数を返す操作である。

$f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$$f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$.

●(5) 原始再帰作用素︵Primitive recursion operator︶: 関数 $g(x_{1},\ldots ,x_{k})$$g(x_{1},\ldots ,x_{k})$と $h(y,z,x_{1},\ldots ,x_{k})$$h(y,z,x_{1},\ldots ,x_{k})$をとり、以下のような関数 $f$$f$を返す操作である。

$f(0,x_{1},\ldots ,x_{k})=g(x_{1},\ldots ,x_{k})$$f(0,x_{1},\ldots ,x_{k})=g(x_{1},\ldots ,x_{k})$,

$f(y+1,x_{1},\ldots ,x_{k})=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$$f(y+1,x_{1},\ldots ,x_{k})=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$.

●(6) μ作用素: 関数 $f(y,x_{1},\ldots ,x_{k})$$f(y,x_{1},\ldots ,x_{k})$をとり、$x_{1},\ldots ,x_{k}$$x_{1},\ldots ,x_{k}$ を引数とする関数 $\mu yf(y,x_{1},\ldots ,x_{k})$$\mu yf(y,x_{1},\ldots ,x_{k})$を返す操作である。関数 $f$$f$は自然数 $\{0,1,...n\}$$\{0,1,...n\}$から自然数 $\{0,1,...n\}$$\{0,1,...n\}$への数論的関数か、または値域 $\{0,1\}$$\{0,1\}$で真偽を示す述語としての指示関数である。

どちらの場合でも、関数 $\mu yf$$\mu yf$は、$f(0,x_{1},\ldots ,x_{k}),f(1,x_{1},\ldots ,x_{k}),...,f(y,x_{1},\ldots ,x_{k})$$f(0,x_{1},\ldots ,x_{k}),f(1,x_{1},\ldots ,x_{k}),...,f(y,x_{1},\ldots ,x_{k})$が全て値を返すとき、$f(y,x_{1},\ldots ,x_{k})=0$$f(y,x_{1},\ldots ,x_{k})=0$ となるような自然数 $y$$y$があれば、そのうちの最小のものを返す。もしそのような $y$$y$がなければ、 $\mu yf$$\mu yf$はそのときの引数 $x_{1},\ldots ,x_{k}$$x_{1},\ldots ,x_{k}$の組み合わせに対して定義されない。

部分μ再帰関数同士を比較する演算子として $\simeq$$\simeq$︵strong equality︶がある。部分関数 $f$$f$と $g$$g$について、

$f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})$$f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})$
が成り立つのは、任意の引数の組み合わせについて、両関数の定義が存在して値が同じであるか、さもなくばどちらも未定義である場合だけである。

決定可能性の問題

ここである疑問が生じる。ここで説明されている計算のアルゴリズムは停止しないのか、である。ここでは﹁計算不能﹂な関数を扱っているのだろうか。計算可能かどうかはどうやって決定されるのか。クリーネは以下のように記している。

まず、以下のような﹁効率的に決定可能な述語﹂について考える。

εyR(x,y) = IF (Ey)R(x,y) THEN ε ="least y such that R(x,y)" ELSE 0.

クリーネは次のように提案している。﹁命題 R(x,0), R(x,1), R(x,2), ... を順に調べていき、真であるものを探す。我々が満足するまで…

﹁しかし、もし NOT_(Ey)R(x,y) であるようなxであれば、探索は際限なく続き何も得られないだろう。アレフ₀ の全命題の評価を完了することは人間計算機には不可能である。

﹁ だがそれにもかかわらず、R(x,y) をうまく選択すれば、εyR(x,y) を効率的に計算可能かもしれない…何らかの効率的な手続きをとれば。

﹁したがって、述語 (Ey)R(x,y) を効率的に決定可能である場合のみ、関数 εyR(x,y) を効率的に計算可能である﹂︵Kleene pp. 317-318︶

そこで、我々の採用しているアルゴリズムが﹁決定可能﹂かどうかをどうやって判断すればよいだろうか。﹁停止判定﹂アルゴリズムを使って停止するかどうかを調べられるだろうか。そのような判定が不可能であるという証明は非常に複雑である。重要な点は、クリーネが全ての全域再帰関数をゲーデル数によって数え上げ、カントールの対角線論法を使って、それ以上の再帰関数が定義可能であることを示したことである。

結論から言えば、μ再帰関数の停止判定はμ再帰関数の体系では不可能であり、チューリングマシンの停止問題と実質的に同じ問題であることが判っている。

他の計算可能性モデルとの等価性

クリーネは以下の最終定理で、﹁チューリングマシンによる計算可能関数﹂と﹁部分μ再帰関数﹂が等価であることを示した。

次のクラスの部分関数は同一の広がりを持つ。すなわち、同じメンバーを持つ。
(a) 部分再帰関数

(b) 何らかの機械で計算可能な関数

(c) 1/1 関数︵チューリングマシンを一方向のテープと1つのシンボルだけに制限したもの︶

さらに、これらは私が定義した関数 Ψ とも同一の広がりを持つ。︵Kleene p. 376︶

クリーネはこれを証明するために、5つの原始再帰関数の作用素とμ作用素をチューリングマシンでエミュレートできることを示し、逆にチューリングマシンの動作を数値化することでその動作をμ再帰関数で表現できることを示した。

正規形定理

クリーネの正規形定理︵英語: Kleene's_T_predicate#Normal_form_theorem︶は、次を主張する: 原始再帰関数 ${\displaystyle U($y)\!} $U(y)\!$と $T(y,e,x_{1},\ldots ,x_{k})\!$$T(y,e,x_{1},\ldots ,x_{k})\!$について、k 個の自由変数を持つμ再帰関数 $f(x_{1},\ldots ,x_{k})\!$$f(x_{1},\ldots ,x_{k})\!$があり、以下を満足する eが存在する。

$f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))$$f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))$.

ここで、e は関数 fのインデックスまたはゲーデル数である。つまり、任意のμ再帰関数は原始再帰関数に1回だけμ作用素を適用することで定義される。

ミンスキー︵1967︶は、ここで定義されたUが基本的に万能チューリングマシンと等価であると述べた。

例

• フィボナッチ数
• マッカーシーの91関数

関連項目

• 再帰理論
• 再帰呼び出し
• 原始再帰関数

外部リンク

• Stanford Encyclopedia of Philosophy entry

参考文献

• Stephen Kleene (1952) Introduction to Metamathematics. Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971); Tenth impression 1991, ISBN 0-7204-2103-9.
• Soare, R. Recursively enumerable sets and degrees. Springer-Verlag 1987.
• Marvin L. Minsky (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.

On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70-71.