algorithm - 什么是超递归算法？

Question

我今天第一次遇到这个词，然后 Wikipedia它的条目并没有告诉我太多信息:

In computability theory, super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.

Answer 1

这里的递归并不是指将自身作为子程序的算法；相反，它指的是递归函数类，这些函数可以由图灵机计算。那么，超递归函数将是图灵机不足以计算的函数，需要更强大的计算模型。

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