超计算

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

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

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

 扩展阅读 
 Mario Antoine Aoun, "Advances in Three Hypercomputation Models ", (2016)
 L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997.  General development of complexity theory for abstract machines that compute on real numbers instead of bits.
Burgin, M. S. (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, v. 270, No. 6, pp. 1289–1293
 Keith Douglas. Super-Turing Computation: a Case Study Analysis  (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. 
 Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007

 Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461–502
 Davis, Martin (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006.  The requested URL /~simon/TEACH/28000/DavisUniversal.pdf was not found on this server. Lecture Notes in Computer Science, 3988 pp. 125–132
 Hagar, A. and Korolev, A., Quantum Hypercomputation—Hype or Computation? , (2007)

 Ord, Toby. Hypercomputation: Computing more than the Turing machine can compute : A survey article on various forms of hypercomputation.
Piccinini, Gualtiero: Computation in Physical Systems 
 Putz, Volkmar and Karl Svozil, Can a computer be "pushed" to perform faster-than-light? , (2010)
 Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts

Mike Stannett, The case for hypercomputation, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 8–24, Special Issue on Hypercomputation
Syropoulos, Apostolos (2008), Hypercomputation: Computing Beyond the Church–Turing Barrier (preview ), Springer. 


外部链接
Hypercomputation Research Network 

Category:計算理論