Μ再帰関数のソースを表示

{{小文字|title=μ再帰関数}}
'''μ再帰関数'''（ミューさいきかんすう、{{lang-en-short|μ-recursive function}}）または'''帰納的関数'''（きのうてきかんすう）とは、[[数理論理学]]と[[計算機科学]]において、直観的に「計算可能」な[[自然数]]から自然数への[[部分関数]]のクラスである。[[計算可能性理論]]では、μ再帰関数は[[チューリングマシン]]で計算可能な関数と正確に一致することが示されている。μ再帰関数は[[原始再帰関数]]（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例として[[アッカーマン関数]]がある。

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

[[計算複雑性理論]]では、全再帰関数の集合を[[R (計算複雑性理論)|'''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）: 任意の自然数 <math>n</math> と <math>k</math> について:
:<math>f(x_1,\ldots,x_k) = n</math>.
:::定数 <math>n</math> は、「初期オブジェクト・ゼロ（initial object 0）」と呼ばれるオブジェクトに後者関数を繰り返し適用することで生成されることがある。
<!-- <math>\lambda x_1,\ldots,x_k[n]</math> is initial.-->
* (2)  '''後者関数'''（Successor function）'''S''': 既に生成されたオブジェクトから別のオブジェクト <math>n+1</math> または <math>n'</math> （<math>n</math> の後者）への逐次的経路
: <math>S(x) \stackrel{\mathrm{def}}{=}  f(x) = x' = x + 1\,</math> 
<!-- <math>\lambda x[x+1]</math>  -->
* (3)  '''射影関数'''（Projection function）'''P<sub>i</sub><sup>k</sup>''' （'''Identity function I<sub>i</sub><sup>k</sup>''' とも）: <math>1 \le i \le k</math> であるような全ての自然数 <math>i</math> について:
: <math>P_i^k \stackrel{\mathrm{def}}{=} f(x_1,\ldots,x_k) = x_i</math>.
* (4)  '''合成作用素'''（Composition operator）: '''置換'''（substitution）とも呼ばれ、関数 <math>h(x_1,\ldots,x_m)</math> と <math>1 \le i \leq m</math> であるような <math>i</math> それぞれについての関数 <math>g_i(x_1,\ldots,x_k)</math> をとり、<math>x_1,\ldots,x_k</math> を以下のようにマップする関数を返す操作である。
:<math>f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))</math>.
* (5)  '''原始再帰作用素'''（Primitive recursion operator）: 関数 <math>g(x_1,\ldots,x_k)</math> と <math>h(y,z,x_1,\ldots,x_k)</math> をとり、以下のような関数  <math>f</math> を返す操作である。
: <math>f(0,x_1,\ldots,x_k) = g(x_1,\ldots,x_k)</math>,
: <math>f(y+1,x_1,\ldots,x_k) = h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k)</math>.

* (6)  '''μ作用素''': 関数 <math>f(y,x_1,\ldots, x_k)</math> をとり、<math>x_1,\ldots, x_k</math> を引数とする関数 <math>\mu y f(y,x_1,\ldots,x_k)</math> を返す操作である。関数 <math>f</math> は自然数 <math>\{ 0, 1, ... n \}</math> から自然数 <math>\{ 0, 1, ... n \}</math> への数論的関数か、または値域 <math>\{ 0, 1 \}</math> で真偽を示す述語としての[[指示関数]]である。
: どちらの場合でも、関数 <math>\mu y f</math> は、<math>f(0,x_1,\ldots, x_k),f(1,x_1,\ldots, x_k),...,f(y,x_1,\ldots, x_k)</math>が全て値を返すとき、<math>f(y,x_1,\ldots, x_k) = 0</math> となるような自然数 <math>y</math> があれば、そのうちの最小のものを返す。もしそのような <math>y</math> がなければ、 <math>\mu y f</math> はそのときの引数 <math>x_1,\ldots,x_k</math> の組み合わせに対して定義されない。

部分μ再帰関数同士を比較する演算子として <math>\simeq</math>（strong equality）がある。部分関数 <math>f</math> と <math>g</math> について、
:<math>f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l)</math> 
が成り立つのは、任意の引数の組み合わせについて、両関数の定義が存在して値が同じであるか、さもなくばどちらも未定義である場合だけである。

== 決定可能性の問題 ==
{{節スタブ}}

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

まず、以下のような「効率的に決定可能な述語」について考える。
:ε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 であれば、探索は際限なく続き何も得られないだろう。アレフ<sub>0</sub> の全命題の評価を完了することは人間計算機には不可能である。
:「  だがそれにもかかわらず、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つの原始再帰関数の作用素とμ作用素をチューリングマシンでエミュレートできることを示し、逆にチューリングマシンの動作を数値化することでその動作をμ再帰関数で表現できることを示した。

== 正規形定理 ==
クリーネの{{日本語版にない記事リンク|正規形定理|en|Kleene's_T_predicate#Normal_form_theorem}}は、次を主張する: 原始再帰関数 <math>U(y)\!</math> と <math>T(y,e,x_1,\ldots,x_k)\!</math> について、''k'' 個の[[自由変数]]を持つμ再帰関数 <math>f(x_1,\ldots,x_k)\!</math> があり、以下を満足する ''e'' が存在する。
:<math>f(x_1,\ldots,x_k) \simeq U(\mu y\, T(y,e,x_1,\ldots,x_k))</math>.
ここで、''e'' は関数 ''f'' の'''インデックス'''または'''[[ゲーデル数]]'''である。つまり、任意のμ再帰関数は原始再帰関数に1回だけμ作用素を適用することで定義される。

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

== 例 ==
* [[フィボナッチ数]]
* [[マッカーシーの91関数]]

== 関連項目 ==
* [[再帰理論]]
* [[再帰呼び出し]]
*[[原始再帰関数]]

== 外部リンク ==
*[http://plato.stanford.edu/entries/recursive-functions/ 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.

{{DEFAULTSORT:みゆうさいきかんすう}}
[[Category:数理論理学]]
[[Category:計算理論]]
[[Category:数学に関する記事|Mさいきかんすう]]

[[ru:Рекурсивная функция (теория вычислимости)#Частично рекурсивная функция]]