递归集与递归函数 [英] Recursive Sets vs Recursive Functions

问题描述

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

What s the difference between a recursive set and recursive function?

推荐答案

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

Recursive functions and recursive sets are terms used in computability theory. Wikipedia defines them as follows:

一组自然数被称为可计算的集合（也称为可确定的，递归的或图灵的）可计算集合），如果有一个图灵机（给定数字n），则在集合中包含n时停止输出1，如果集合中没有n则停止输出0。如果存在一个图灵机，在输入n处暂停并返回输出f（n），则从自然数到其自身的函数f是递归或（图灵）可计算函数。

A set of natural numbers is said to be a computable set (also called a decidable, recursive, or Turing computable set) if there is a Turing machine that, given a number n, halts with output 1 if n is in the set and halts with output 0 if n is not in the set. A function f from the natural numbers to themselves is a recursive or (Turing) computable function if there is a Turing machine that, on input n, halts and returns output f(n).

在这种情况下，递归函数并不意味着用编程语言调用的函数。满足上述定义要求的任何 mathematical 函数都是递归函数，包括琐碎的函数，例如恒等函数或将所有数字映射为1的函数（即，不管输入如何，都返回数字1）。

In this context, a recursive function does not mean a function in a programming language that calls itself. Any mathematical function that meets the requirements of the definition above is a recursive function, including trivial ones such as the identity function or the function mapping all numbers to 1 (i.e. returns the number 1 regardless of input).

这篇关于递归集与递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！