翻訳と辞書 Words near each other ・ M・ジョン・ハリスン ・ M・チュルリョーニス美術館 ・ M・ナイト・シャマラン ・ M・バイソン ・ M・バタフライ ・ M・パテー商会 ・ M・ブラック ・ M・ミランコビッチ ・ M・中村 ・ M作戦 ・ M再帰関数 ・ M君事件 ・ M型小惑星 ・ M型潜水艦 ・ M字 ・ M字ビターン ・ M字開脚 ・ M宇宙ハンター星雲人 ・ M帯 ・ M式ATS Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク M再帰関数 ： ウィキペディア日本語版 Μ再帰関数 μ再帰関数（ミューさいきかんすう、）または帰納的関数（きのうてきかんすう）は、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。 また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。 計算複雑性理論では、全再帰関数の集合をRと称する。 == 定義 == μ再帰関数（または部分μ再帰関数）は、有限個の自然数の引数をとり、1つの自然数を返す部分関数である。μ再帰関数は初期関数を含み、合成や原始再帰やμ作用素において閉じている、部分関数の最小のクラスである。 原始再帰関数もほぼ同じ定義となるが、全域関数という点が異なる。また、原始再帰関数は、3つの基本関数（定数関数、後者関数、射影関数）と2つの作用素（合成と原始再帰）で定義されるが、μ再帰関数にはさらにμ作用素が登場する。これはアッカーマン関数のように原始再帰関数でない全域再帰関数を定義するためである。μ再帰関数においてμ作用素は計算を終了させる。μ作用素は無制限探索演算子として働き、（全域関数の定義から）無制限ではあるが何らかの手段（帰納的定義など）で最終的に数を生成し計算を終わらせるのである。 しかし、無制限μ作用素自身が部分的な場合（つまり、ある数について数を返せないことがある場合）、それを使って定義された関数も部分関数となり、一部の数については値が定義されない。この場合、無制限という性質上、μ作用素は永遠に探索を続け、計算を終了して数を返すことがない。アルゴリズムによっては、"u" という記号で 「決定不能（undecided）」を表し、計算を終了させるとする場合もある（例えば、Kleene (1952) pp. 328ff）。換言すれば、部分μ再帰関数は部分μ作用素を使うため、全域的でない可能性がある。全域μ再帰関数（total μ-recursive functions）は部分μ再帰関数の部分集合である。 最初の3つの関数を「初期関数（initial functions）」または「基本関数（basic functions)」と呼ぶ。以下の定義は Kleene (1952) p. 219 に基づいている。その他の記号体系については「記号体系」の節を参照されたい。 * (1) 定数関数（Constant function）: 任意の自然数 $n$ と $k$ について: :$f(x\_1,\backslash ldots,x\_k)\; =\; n$. :::定数 $n$ は、「初期オブジェクト・ゼロ（initial object 0）」と呼ばれるオブジェクトに後者関数を繰り返し適用することで生成されることがある。 * (2) 後者関数（Successor function）S: 既に生成されたオブジェクトから別のオブジェクト $n+1$ または $n\text{'}$ （$n$ の後者）への逐次的経路 : $S(x)\; \backslash stackrel\; f(x)\; =\; x\text{'}\; =\; x\; +\; 1\backslash ,$ * (3) 射影関数（Projection function）Pik （Identity function Iik とも）: $1\; \backslash le\; i\; \backslash le\; k$ であるような全ての自然数 $i$ について: : $P\_i^k\; \backslash stackrel\; f(x\_1,\backslash ldots,x\_k)\; =\; x\_i$. * (4) 合成作用素（Composition operator）: 置換（substitution）とも呼ばれ、関数 $h(x\_1,\backslash ldots,x\_m)$ と $1\; \backslash le\; i\; \backslash leq\; m$ であるような $i$ それぞれについての関数 $g\_i(x\_1,\backslash ldots,x\_k)$ をとり、$x\_1,\backslash ldots,x\_k$ を以下のようにマップする関数を返す操作である。 :$f(x\_1,\backslash ldots,x\_k)\; =\; h(g\_1(x\_1,\backslash ldots,x\_k),\backslash ldots,g\_m(x\_1,\backslash ldots,x\_k))$. * (5) 原始再帰作用素（Primitive recursion operator）: 関数 $g(x\_1,\backslash ldots,x\_k)$ と $h(y,z,x\_1,\backslash ldots,x\_k)$ をとり、以下のような関数 $f$ を返す操作である。 : $f(0,x\_1,\backslash ldots,x\_k)\; =\; g(x\_1,\backslash ldots,x\_k)$, : $f(y+1,x\_1,\backslash ldots,x\_k)\; =\; h(y,f(y,x\_1,\backslash ldots,x\_k),x\_1,\backslash ldots,x\_k)$. * (6) μ作用素: 関数 $f(y,x\_1,\backslash ldots,\; x\_k)$ をとり、$x\_1,\backslash ldots,\; x\_k$ を引数とする関数 $\backslash mu\; y\; f(y,x\_1,\backslash ldots,x\_k)$ を返す操作である。関数 $f$ は自然数 $\backslash$ から自然数 $\backslash$ への数論的関数か、または値域 $\backslash$ で真偽を示す述語としての指示関数である。 : どちらの場合でも、関数 $\backslash mu\; y\; f$ は、$f(0,x\_1,\backslash ldots,\; x\_k),f(0,x\_1,\backslash ldots,\; x\_k),...,f(y,x\_1,\backslash ldots,\; x\_k)$が全て値を返すとき、$f(y,x\_1,\backslash ldots,\; x\_k)\; =\; 0$ となるような自然数 $y$ があれば、そのうちの最小のものを返す。もしそのような $y$ がなければ、 $\backslash mu\; y\; f$ はそのときの引数 $x\_1,\backslash ldots,x\_k$ の組み合わせに対して定義されない。 部分μ再帰関数同士を比較する演算子として $\backslash simeq$（strong equality）がある。部分関数 $f$ と $g$ について、 :$f(x\_1,\backslash ldots,x\_k)\; \backslash simeq\; g(x\_1,\backslash ldots,x\_l)$ が成り立つのは、任意の引数の組み合わせについて、両関数の定義が存在して値が同じであるか、さもなくばどちらも未定義である場合だけである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Μ再帰関数」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 μ-recursive function 」があります。 スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.