什么是超递归算法？

Question

24

今天我第一次遇到这个术语，但维基百科上对其的解释并不多：

在可计算性理论中，超递归算法是普通算法的推广，更加强大，即可以计算图灵机无法计算的问题。

- Ferruccio

3

一旦你得到答案，你也可以编辑标签！ - Mike Christensen

那个标签真的有用吗？ - MarcioB

3

由于非可计算算法基本上无法在软件中实现，所以可能不行。 - David Eisenstat

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chepner · Accepted Answer

递归在这里并不是指使用自身作为子程序的算法，而是指递归函数的类别，即可以通过图灵机计算的函数。那么超递归函数将是一种需要更强大的计算模型才能计算的函数，超越了图灵机的计算能力。

例如，停机问题需要超递归算法，因为它不能用普通的图灵机来解决。