Hypercomputation

From Wikipedia, the free encyclopedia

Hypercomputation refers to various hypothetical methods for the computation of non-Turing-computable functions (see also supertask). The term was first introduced by Jack Copeland. 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.

Contents 1 History 2 Hypercomputer proposals 3 Bibliography 4 See also 5 References 6 External links

[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.^[1]

[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.
• 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.^[2]
• A real computer (a sort of idealized analog computer) might be able to perform hypercomputation ^[3] 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.^[4] 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 (ie turing) computer couldn't already). ^[5]
• 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) could also permit hypercomputation.^{[citation needed]}

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

[edit] 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.^{[citation needed]}

[edit] See also

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

[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. (link is to ScienceDirect website copy)
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, Hypercomputation: Computing Beyond the Church-Turing Barrier, 2008

[edit] External links

• Hypercomputation Research Network
• Toby Ord, Hypercomputation: computing more than the Turing machine
• Toby Ord, The many forms of hypercomputation
• Paolo Cotogno, Hypercomputation and the Physical Church-Turing thesis