From Wikipedia, the free encyclopedia

Jump to: navigation, search

Hypercomputation refers to various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms (see also supertask). The term was first introduced in 1999 by Jack Copeland and Diane Proudfoot[1]. A similar term is super-Turing computation, was previously introduced and demonstrated by Hava Siegelmann. Hypercomputation may have the additional connotation of entertaining the possibility that such a device could be physically realizable. Some models have been proposed, already by Siegelmann, 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.


[edit] 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.[2]

[edit] 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.[3]
  • 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.[4]
  • A real computer (a sort of idealized analog computer) might be able to perform hypercomputation [5] 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.[6] This is not possible using the standard qubit-model quantum computer, because it is proven that a regular quantum computer is PSPACE-reducible (a quantum computer running in polynomial time can be simulated by a classical computer running in polynomial space). [7]
  • 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.[8][9]
  • In the early 1990s, Hava Siegelmann proposed a new computational model, the Artificial Recurrent Neural Network (ARNN), and proved that it could perform hypercomputation. It is based on evolving an artificial neural network through an infinite succession of states.[10].

[edit] See also

[edit] Bibliography

  1. ^ Copeland and Proudfoot, Alan Turing's forgotten ideas in computer science. Scientific American, April 1999.
  2. ^ "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)
  3. ^ See for example Shagrir, O. (June 2004). "Super-tasks, accelerating Turing machines and uncomputability". Theor. Comput. Sci. 317, 1-3: 105-114. doi:10.1016/j.tcs.2003.12.007. http://edelstein.huji.ac.il/staff/shagrir/papers/Supertasks_Accelerating_Turing_Machines_and_Uncomputability.pdf. 
  4. ^ Joel David Hamkins and Andy Lewis, Infinite time Turing machines, Journal of Symbolic Logic, 65(2):567-604, 2000.[1]
  5. ^ 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"[2] p. 12
  6. ^ There have been some claims to this effect; see Tien Kieu (2003). "Quantum Algorithm for the Hilbert's Tenth Problem". Int. J. Theor. Phys. 42: 1461–1478. doi:10.1023/A:1025780028846. http://www.arxiv.org/pdf/quant-ph/0110136. . & the ensuing literature. Errors have been pointed out in Kieu's approach by Warren D. Smith in Three counterexamples refuting Kieu’s plan for “quantum adiabatic hypercomputation”; and some uncomputable quantum mechanical tasks
  7. ^ Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [3]
  8. ^ Todd A. Brun, Computers with closed timelike curves can solve hard problems, Found.Phys.Lett. 16 (2003) 245-253.[4]
  9. ^ S. Aaronson and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent [5]
  10. ^ Verifying Properties of Neural Networks p.6

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.[citation needed]

[edit] References

  1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
  2. Hava Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
  3. Hava Siegelmann. The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472.
  4. Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
  5. 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.
  6. On the computational power of neural nets
  7. Toby Ord. Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation.
  8. Apostolos Syropoulos (2008), Hypercomputation: Computing Beyond the Church-Turing Barrier, Springer. ISBN 9780387308869
  9. Burgin, M. S. (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, v. 270, No. 6, pp. 1289-1293
  10. Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0387955690
  11. Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007
  12. Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461-502
  13. Martin Davis (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
  14. Hagar, A. and Korolev, A. (2007) Quantum Hypercomputation – Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
  15. Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts

[edit] External links

Personal tools