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. Look up computation in Wiktionary, the free dictionary. ... It has been suggested that recursive function be merged into this article or section. ... B. Jack Copeland is Professor of Philosophy at the University of Canterbury, Christchurch, New Zealand. ... Super-Turing computation is any form of computation that cannot be performed by a Turing machine. ... Please refer to Real vs. ...

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 could not, in fact, be physically realized (see the Turing quote). Alan Turing is often considered the father of modern computer science. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ...

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 is 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 the halting problem, 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^[1]. 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). ^[2]
• 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.

At this stage, none of these devices seem physically plausible. Thus, hypercomputers are likely to remain as mathematical models. Time dilation is the phenomenon whereby an observer finds that anothers clock which is physically identical to their own is ticking at a slower rate as measured by their own clock. ... In computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. ... A page from the Bombardiers Information File (BIF) that describes the components and controls of the Norden bombsight. ... In mathematics, the real numbers may be described informally in several different ways. ... In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. ... // ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ... Johnson-Nyquist noise (sometimes thermal noise, Johnson noise or Nyquist noise) is the noise generated by the equilibrium fluctuations of the electric current inside an electrical conductor, which happens without any applied voltage, due to the random thermal motion of the charge carriers (the electrons). ... Fig. ... Fig. ... It has been suggested that recursive function be merged into this article or section. ... To meet Wikipedias quality standards and make it more accessible, this article needs a better explanation of technical details or more context regarding applications or importance to make it more accessible to a general audience, or at least to technical readers outside this specialty. ... The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers. ... In physics, spacetime is a mathematical model that combines three-dimensional space and one-dimensional time into a single construct called the space-time continuum, in which time plays the role of the 4th dimension. ... A Malament-Hogarth (M-H) spacetime is a relativistic spacetime that possesses the following property: there exists a worldline λ of infinite proper length that lies to the past of some event p. ... In special relativity, a light cone is the pattern describing the temporal evolution of a flash of light in Minkowski spacetime. ...

See also

• Church-Turing thesis
• Oracle machine
• Computation

In computability theory the Church–Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ... Look up computation in Wiktionary, the free dictionary. ...

Notes

1. ^ 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"".]
2. ^ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. 

Hilberts problems are a list of 23 problems in mathematics put forth by German mathematician David Hilbert in the Paris conference of the International Congress of Mathematicians in 1900. ...

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. Thomas Natschläger et al. the "Liquid Computer": A Novel Strategy for Real-Time Computing on Time Series
7. http://www.nature.com/nsu/010329/010329-8.html A Nature article on the above.
8. On the computational power of neural nets