Hypercomputation

From Wikipedia, the free encyclopedia

Hypercomputation refers to various proposed methods for the computation of non-Turing-computable functions. 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 real-valued functions that are exact rather than approximate.

Contents 1 History 2 Theoretical and conceptual possibilities for a hypercomputer 3 See also 4 Notes 5 References

[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 present. Turing's writing made it clear that oracle machines were only mathematical abstractions, and were not thought of as physically realisable.^[1]

[edit] Theoretical and conceptual possibilities for a hypercomputer

• 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).
• A real computer (a sort of idealized analog computer) might be able to perform hypercomputation 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^[2]. Such a system could not be an ordinary qubit quantum computer because it has been proved that regular quantum computers are Turing reducible (they may yield speedup for some problems, but they don't allow solving new problems). ^[3]
• A digital computer in a special kind of spacetime, called a Malament-Hogarth spacetime, can perform an infinite number of operations while remaining in the past light cone of a particular spacetime event.
• 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.

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

[edit] See also

• Church-Turing thesis
• Oracle machine
• Computation

[edit] Notes

1. ^ "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)
2. ^ 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. . & the ensuing literature. Errors have been pointed out in Kieu's paper (cf. Boris Tsirelson. "The quantum algorithm of Kieu does not solve the Hilbert's tenth problem". ) and, in more recent papers, Kieu has downgraded his claims from "a quantum algorithm that solves an uncomputable problem" to "a quantum algorithm that might be solving an uncomputable problem". [Tien Kieu. "Reply to "The quantum algorithm of Kieu does not solve the Hilbert's tenth problem"". ]
3. ^ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. 

[edit] References

1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
2. Hava Siegelman. 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 or complex 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.