超计算

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

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

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

参见

• 黑箱
• 图灵机
• 图灵归约
• 交互式证明系统
• 大型语言模型
• 隨機預言機

扩展阅读

• Mario Antoine Aoun, "[http://www.ejtp.com/articles/ejtpv13i36p169.pdf 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. [https://www.philosopher-animal.com/papers/take6c.PDF 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) [https://web.archive.org/web/20160314161451/http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_MINDS_AND_MACHINES/VOLUME_12_NO_4/NV6361035557Q678.pdf Hypercomputation], Minds and machines, v. 12, pp. 461–502
• Davis, Martin (2006), "[https://wayback.archive-it.org/all/20080221162316/http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf 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., [https://philsci-archive.pitt.edu/archive/00003180/ Quantum Hypercomputation—Hype or Computation?] , (2007)

*

• Ord, Toby. [https://arxiv.org/abs/math/0209332 Hypercomputation: Computing more than the Turing machine can compute] : A survey article on various forms of hypercomputation.

Piccinini, Gualtiero: [https://plato.stanford.edu/entries/computation-physicalsystems/ Computation in Physical Systems*]

• Putz, Volkmar and Karl Svozil, [https://arxiv.org/abs/1003.1238 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, [https://web.archive.org/web/20160304053941/http://research.cs.queensu.ca/home/akl/cisc879/papers/PAPERS_FROM_APPLIED_MATHEMATICS_AND_COMPUTATION/Special_Issue_on_Hypercomputation/stannett%5B1%5D.pdf 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), [https://www.springer.com/computer/foundations/book/978-0-387-30886-9 Hypercomputation: Computing Beyond the Church–Turing Barrier]* ([https://books.google.com/books?id=5gVOf_OQa04C preview] ), Springer.
*

外部链接
*[https://www.hypercomputation.net/ Hypercomputation Research Network]