μみゅー再帰さいき関数かんすう

μみゅー再帰さいき関数かんすう（ミューさいきかんすう、英えい: μみゅー-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$ と $k$ について:

$f(x_{1},\ldots ,x_{k})=n$.

定数ていすう $n$ は、「初期しょきオブジェクト・ゼロ（initial object 0）」と呼よばれるオブジェクトに後者こうしゃ関数かんすうを繰くり返かえし適用てきようすることで生成せいせいされることがある。

• (2) 後者こうしゃ関数かんすう（Successor function）S: 既すでに生成せいせいされたオブジェクトから別べつのオブジェクト $n+1$ または $n'$ （$n$ の後者こうしゃ）への逐次ちくじ的てき経路けいろ

$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$ であるような全すべての自然しぜん数すう $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})$ と $1\leq i\leq m$ であるような $i$ それぞれについての関数かんすう $g_{i}(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}))$.

• (5) 原始げんし再帰さいき作用素さようそ（Primitive recursion operator）: 関数かんすう $g(x_{1},\ldots ,x_{k})$ と $h(y,z,x_{1},\ldots ,x_{k})$ をとり、以下いかのような関数かんすう $f$ を返かえす操作そうさである。

$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})$.

• (6) μみゅー作用素さようそ: 関数かんすう $f(y,x_{1},\ldots ,x_{k})$ をとり、$x_{1},\ldots ,x_{k}$ を引数ひきすうとする関数かんすう $\mu yf(y,x_{1},\ldots ,x_{k})$ を返かえす操作そうさである。関数かんすう $f$ は自然しぜん数すう $\{0,1,...n\}$ から自然しぜん数すう $\{0,1,...n\}$ への数かず論ろん的てき関数かんすうか、または値域ちいき $\{0,1\}$ で真偽しんぎを示しめす述語じゅつごとしての指示しじ関数かんすうである。

どちらの場合ばあいでも、関数かんすう $\mu yf$ は、$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$ となるような自然しぜん数すう $y$ があれば、そのうちの最小さいしょうのものを返かえす。もしそのような $y$ がなければ、 $\mu yf$ はそのときの引数ひきすう $x_{1},\ldots ,x_{k}$ の組くみ合あわせに対たいして定義ていぎされない。

部分ぶぶんμみゅー再帰さいき関数かんすう同士どうしを比較ひかくする演算えんざん子ことして $\simeq$（strong equality）がある。部分ぶぶん関数かんすう $f$ と $g$ について、

$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）は、次つぎを主張しゅちょうする: 原始げんし再帰さいき関数かんすう $U(y)\!$ と $T(y,e,x_{1},\ldots ,x_{k})\!$ について、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}))$.

ここで、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.