跳转到内容

超计算

维基百科,自由的百科全书

超计算超图灵计算可以输出非图灵可计算结果的计算模型。例如,一台可以解决停机问题的机器可算作一台超计算机;可以正确推演皮亚诺算术中每一个状态的机器亦然。

邱奇-图灵论题指出,任何可以用有限算法以纸笔计算的"可有效计算"函数都能被图灵机计算。超计算机能计算图灵机无法计算、即邱奇-图灵论题中不可计算的的函数。

严格说来概率图灵机的输出是不可计算的。然而,大多数超计算方向的文献更关注有用的计算而非随机、不可计算的函数。

扩展阅读

外部链接