递归集与递归函数

Question

递归集和递归函数之间有什么区别？

Answer 1

递归函数和递归集是可计算性理论中使用的术语.维基百科将它们定义如下:

一组自然数被称为可计算集(也称为可判定,递归或图灵可计算集),如果存在图灵机,给定数n,如果n在集合中则停止输出1并停止如果n不在集合中,则输出0.如果有一个图灵机在输入n上停止并返回输出f(n),则从自然数到自身的函数f是递归或(图灵)可计算函数.

在这种情况下,递归函数并不意味着调用自身的编程语言中的函数.满足上述定义要求的任何数学函数都是递归函数,包括平凡函数,例如标识函数或将所有数字映射到1的函数(即,无论输入如何都返回数字1).

Answer 2

这些术语的含义取决于您的背景.如果我们纯粹从编写程序的角度讨论它们,那么递归集就没有多大意义; 然而,它可能只是我遇到过它.也就是说,递归函数是在执行时调用自身的函数.一个的计算^日 斐波那契数是通常呈现的典型的例子:

/// <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);
 }
}

也就是说,在计算机科学,特别是计算理论的背景下,这些术语的另一个背景是在讨论形式语言时.在此上下文中,递归集被定义为具有可解决的成员资格问题的集合.例如,我们知道所有自然数的集合ℕ是一个递归集,因为我们可以定义一个递归函数,如下所示:

设f被定义为函数,其中 f(x)= 1如果x∈ℕ且 f(x)= 0,如果x∉∉

递归集的概念对于可计算性的概念很重要,因为它导致递归可枚举集,这是一种可以由图灵机识别的语言(即图灵可识别的).这些是图灵机可能或可能无法确定给定字符串是否是语言成员的语言,或者换句话说,机器可以接受,拒绝或循环.这与图灵可判定语言形成对比,该语言机器将进入给定输入字符串的接受或拒绝状态.

这是递归函数的概念发挥作用,因为递归函数(或总递归函数)可以由图灵机计算并停止每个输入.其中,只能为图灵机计算部分递归函数,而不能保证停止行为.或者本质上,递归函数是递归集的对应物.

因此,为了将问题带回原始问题,在计算理论的上下文中,递归集是可以生成(即枚举)或通过图灵机上的递归函数测试成员资格的集合.

进一步阅读:

• M. Sipser - 计算理论导论(第二版)
• JE Hopcroft,R.Motwani,JD Ullman - 自动机理论,语言和计算导论(第三版)
• HR Lewis,CH Papadimitriou - 计算理论的要素(第二版)
• FD Lewis - 理论计算机科学基础(数字文本)

Answer 3

也许问题应该是"为什么'递归'这个词用于描述集合和函数？"

正如Greg Hewgill在评论中指出的那样,"绿色"这个词可以应用于苹果和汽车,但这并不意味着苹果和汽车之间的关系.

我认为维基百科的引用使用术语"递归"作为"可计算"的同义词 - 我们作为程序员,会谨慎地同意,但仅限于某些情况.