Hypercomputation

Hypercomputation refers to various hypothetical methods for the computation of non-Turing-computable functions (see also supertask). The term was first introduced in 1999 by Jack Copeland and Diane Proudfoot [Copeland and Proudfoot, " [http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=94B166BF-E481-47FA-80C8-112C6BAF404 Alan Turing's forgotten ideas in computer science] ". Scientific American, April 1999.] . A similar term is super-Turing computation, though to some hypercomputation may have the additional connotation of entertaining the possibility that such a device could be physically realizable. Some models have been proposed, such as neural networks with real numbers as weights, the ability to carry out infinitely many computations simultaneously, or the ability to perform non-Turing computable operations, such as limits or integrations on general (i.e. not just trivial) real-valued continuous functions that are exact rather than approximate.

History

A model more powerful than Turing machines was introduced by Alan Turing in his 1939 paper "Systems of logic based on ordinals". This paper investigated mathematical systems in which an oracle was available, which could compute a single arbitrary (non-recursive) function from naturals to naturals. He used this device to prove that even in those more powerful systems, undecidability is still present. Turing's writing made it clear that oracle machines were only mathematical abstractions, and were not thought of as physically realisable. ["Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper "Systems of Logic Based On Ordinals")]

Hypercomputer proposals

*A Turing machine that can "complete" infinitely many steps. Simply being able to run for an unbounded number of steps forever, (i.e. potential infinity) does not suffice. One proposed example uses time dilation to allow a computer to spend an infinite amount of time performing a computation while a finite amount of time passes for an observer (it would require an infinite amount of energy to perform this calculation--see Malament-Hogarth spacetime). Another example is the Zeno machine (inspired by Zeno's paradox), a purely mathematical model. The Zeno machine performs its first computation step in (say) 1 minute, the second step in ½ minute, the third step in ¼ minute, etc. By summing the infinite geometric series 1+½+¼+... we see that the machine performs infinitely many steps in a total of 2 minutes. However, some people claim that, following the reasoning from Zeno's paradox, Zeno machines are not just physically impossible, but logically impossible.
*The infinite time Turing machine is a generalization of the Zeno machine, that can perform infinitely long computations whose steps are enumerated by potentially transfinite ordinal numbers. It models an otherwise-ordinary Turing machine for which non-halting computations are completed by entering a special state reserved for reaching a limit ordinal and to which the results of the preceding infinite computation are available. [Joel David Hamkins and Andy Lewis, Infinite time Turing machines, "Journal of Symbolic Logic", 65(2):567-604, 2000. [http://jdh.hamkins.org/Publications/2000e] ]
*A real computer (a sort of idealized analog computer) might be able to perform hypercomputation [Arnold Schönhage, "On the power of random access machines", in "Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP), pages 520-529, 1979. Source of citation: Scott Aaronson, "NP-complete Problems and Physical Reality" [http://www.scottaaronson.com/papers/npcomplete.pdf] p. 12] if physics admits general real variables (not just computable reals), and these are in some way "harnessable" for computation. This might require quite bizarre laws of physics (for example, a measurable physical constant with an oracular value, such as Chaitin's constant), and would at minimum require the ability to measure a real-valued physical value to arbitrary precision despite thermal noise and quantum effects.
*A quantum mechanical system which somehow uses (for example) an infinite superposition of states to compute a non-computable function. [There have been some claims to this effect; see cite journal | author = Tien Kieu | title = Quantum Algorithm for the Hilbert's Tenth Problem | journal = Int. J. Theor. Phys. | year = 2003 | volume = 42 | url = http://www.arxiv.org/pdf/quant-ph/0110136 | pages = 1461–1478 | doi = 10.1023/A:1025780028846. & the ensuing literature. Errors have been pointed out in Kieu's approach by Warren D. Smith in [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TY8-4JD0GX5-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=a63612cc7522010ee340e8ddada13779 Three counterexamples refuting Kieu’s plan for “quantum adiabatic hypercomputation”; and some uncomputable quantum mechanical tasks] ] This might not be possible using the standard qubit-model quantum computer, because it is conjectured and widely-held that regular quantum computers are Turing reducible (they may yield speedup for some problems, but they may not solve problems that an ordinary (i.e. Turing) computer couldn't already). [ cite book | author=Michael Nielsen and Isaac Chuang | title=Quantum Computation and Quantum Information | publisher=Cambridge University Press | location=Cambridge | year=2000 | id=ISBN 0-521-63503-9 ]
* A technique known as fair nondeterminism or unbounded nondeterminism may allow the computation of noncomputable functions. There is dispute in the literature over whether this technique is coherent, and whether it actually allows noncomputable functions to be "computed".
*The use of closed timelike curves (CTC), contrary to the beliefs of some, do not appear to permit hypercomputation, since they do not provide the unbounded amount of storage that an infinite computation would require. However, access to a CTC may allow the rapid solution to PSPACE-complete problems, a complexity class which while Turing-decidable is generally considered computationally intractable. [Todd A. Brun, "Computers with closed timelike curves can solve hard problems", Found.Phys.Lett. 16 (2003) 245-253. [http://arxiv.org/abs/gr-qc/0209061] ] [S. Aaronson and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent [http://scottaaronson.com/papers/ctc.pdf] ]

As long as there is no physically plausible way to build such a device, hypercomputers will exist only as mathematical models.

ee also

* Church-Turing thesis
* Oracle machine
* Zeno machine
* Computation
* Supertask
* Zeno paradox

Bibliography

Note: Kieu does not seem to have down graded his claim in his reply to Tsirelson's paper. He points out that Tsirelson's argument may be flawed or of limited applicability to his theorem. Fact|date=March 2008

References

#Alan Turing, "Systems of logic based on ordinals", Proc. London math. soc., 45, 1939
#Hava Siegelmann. "Neural Networks and Analog Computation: Beyond the Turing Limit" Boston: Birkhäuser.
#Hava Siegelmann. [http://dx.doi.org/doi:10.1016/S0304-3975(96)00087-4 "The simple dynamics of super Turing theories"] ; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472. (link is to ScienceDirect website copy)
#Keith Douglas. " [http://www.philosopher-animal.com/papers/take6c.PDF Super-Turing Computation: a Case Study Analysis] " (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
#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.
# [ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z On the computational power of neural nets]
#Toby Ord. [http://arxiv.org/abs/math/0209332 "Hypercomputation: Computing more than the Turing machine can compute"] : A survey article on various forms of hypercomputation.
#Apostolos Syropoulos (2008), "Hypercomputation: Computing Beyond the Church-Turing Barrier", Springer. ISBN 9780387308869
# Burgin, M. S. (1983) Inductive Turing Machines, "Notices of the Academy of Sciences of the USSR", v. 270, No. 6, pp. 1289-1293
# Mark Burgin (2005), "Super-recursive algorithms", Monographs in computer science, Springer. ISBN 0387955690
# 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
# Martin Davis (2006), " [http://people.cs.uchicago.edu/~simon/TEACH/28000/DavisUniversal.pdf The Church–Turing Thesis: Consensus and opposition] ". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
# Hagar, A. and Korolev, A. (2007) Quantum Hypercomputation – Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
# Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts

External links

* [http://www.hypercomputation.net/ Hypercomputation Research Network]
* [http://arxiv.org/abs/math/0209332 Toby Ord, "Hypercomputation: computing more than the Turing machine"]
* [http://www.amirrorclear.net/academic/papers/many-forms.pdf Toby Ord, "The many forms of hypercomputation"]
* [http://citeseer.ist.psu.edu/cotogno03hypercomputation.html Paolo Cotogno, "Hypercomputation and the Physical Church-Turing thesis"]