问递归集与递归函数

EN

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

一个自然数集合称为可计算集合(也称为可判定、递归或图灵可计算集合)，如果图灵机给定一个数字n，则如果n在该集合中，则停止输出1，如果n不在该集合中，则停止输出0。从自然数到其自身的函数f是递归函数或(图灵)可计算函数，如果存在图灵机，该图灵机在输入n时停止并返回输出f(n)。

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

也许这个问题应该是“为什么要用‘递归’这个词来描述集合和函数？”

正如Greg Hewgill在他的评论中指出的那样，“绿色”这个词可以用在苹果和汽车上，但这并不意味着苹果和汽车之间的关系。

我认为维基百科的引文使用了“递归”一词作为“可计算”的同义词--作为程序员，我们会谨慎地同意这一点，但只有在某些情况下才会这样做。