3

再帰集合と再帰関数の違いは何ですか？

4

3 に答える 3

9

再帰関数と再帰集合は、計算可能性理論で使用される用語です。ウィキペディアはそれらを次のように定義しています。

自然数の集合は、数値 n が与えられ、n が集合内にあり停止する場合に出力 1 で停止するチューリング マシンがある場合、計算可能な集合 (決定可能集合、再帰集合、またはチューリング計算可能集合とも呼ばれます) と呼ばれます。 n がセットにない場合、出力は 0 です。自然数からそれ自体への関数 f は、入力 n で停止して出力 f(n) を返すチューリング マシンがある場合、再帰的または (チューリング) 計算可能な関数です。

このコンテキストでは、再帰関数は、それ自体を呼び出すプログラミング言語の関数を意味しません。上記の定義の要件を満たす数学関数は再帰関数であり、恒等関数やすべての数値を 1 にマッピングする関数 (つまり、入力に関係なく数値 1 を返す) などの単純なものも含まれます。

于 2009-12-05T21:47:52.230 に答える
6

これらの用語の意味は、コンテキストによって異なります。プログラムを書くという観点から純粋にそれらを議論していたなら、再帰集合はあまり意味がありません。しかし、私はまだそれに遭遇しただけかもしれません。つまり、再帰関数は実行時に自分自身を呼び出す関数です。番目の フィボナッチ数の計算は、一般的に提示される古典的な例です。

/// <summary>A C# implementation of a function to return the nth Fibonacci number.</summary>
private static int Fibonacci(int n) {
 if (n <= 2) {
  return 1;
 } else {
  return Fibonacci(n - 1) + Fibonacci(n - 2);
 }
}

とは言うものの、コンピュータ サイエンス、特に計算理論の文脈におけるこれらの用語のもう 1 つの文脈は、形式言語について議論する場合です。このコンテキストでは、再帰的な集合は、解決可能なメンバーシップの問題がある集合であると定義されます。たとえば、次のように再帰関数を定義できるため、すべての自然数の集合 ℕ は再帰集合であることがわかります。

fを、 x ∈ ℕの 場合f (x) = 1 、 x ∉ ℕ の場合f(x) = 0である関数として定義します。

再帰集合の概念は、計算可能性の概念にとって重要です。これは、チューリング マシンによって認識できる言語である再帰的に列挙可能な集合につながるためです(つまり、チューリング認識可能)。これらは、指定された文字列が言語のメンバーであるかどうかをチューリング マシンが判断できる場合とできない場合がある言語です。つまり、機械はを受け入れるか、拒否するか、ループするかのいずれかです。これは、マシンが特定の入力文字列に対して受け入れ状態または拒否状態になるチューリング決定可能言語とは対照的です。

これは、再帰関数 (または総再帰関数) がチューリング マシンによって計算され、すべての入力に対して停止するため、再帰関数の概念が作用する場所です。部分再帰関数はチューリングマシンに対してのみ計算でき、動作の停止に関しては保証されていません。または、本質的に、再帰関数は再帰セットの対応物です。

したがって、元の質問に戻すために、計算理論のコンテキストでは、再帰セットとは、チューリングマシンの再帰関数によって生成される (つまり、列挙される) か、メンバーシップをテストできるものです。

参考文献：

于 2009-12-06T05:51:29.807 に答える
5

おそらく、「集合と関数の両方を説明するために「再帰的」という言葉が使用されるのはなぜですか?」という質問になるはずでした。

Greg Hewgill 氏がコメントで指摘したように、「グリーン」という言葉はリンゴと車に適用できますが、これはリンゴと車の関係を意味するものではありません。

ウィキペディアからの引用では、「計算可能」の同義語として「再帰的」という用語が使用されていると思います。これは、プログラマーとして慎重に同意しますが、特定のコンテキストでのみです。

于 2009-12-05T21:25:12.637 に答える