Hypercomputation

From Exampleproblems

Hypercomputation refers to various proposed methods for the computation of non-Turing-computable functions. A similar term is super-Turing computation but hypercomputation has an additional sense of believing that any such device is physically realizable. Some models have been proposed, such as neural networks with real numbers as weights, the ability to carry out uncountably many computations simultaneously, or the ability to perform non-Turing computable operations, as limits or integrations.

Contents 1 History 2 The challenge of hypercomputation 3 Theoretical possibilities for a hypercomputer 4 See also 5 Notes 6 References

History

It is often believed that the concept of hypercomputation was first introduced by Alan Turing; this is based on a misunderstanding of Turing´s work in his seminal 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 in order to prove that even in those more powerful systems, undecidability is present. Turing suggested in his original paper that oracle machines were only mathematical abstractions which could not be physically realized.

The challenge of hypercomputation

Today, algorithmic information theory helps us understand what is required for hypercomputation better. The hallmark of a hypercomputer is that it can solve the general halting problem, a feat impossible for ordinary computers. However, a normal computer can calculate the halting predicate of any program given the halting probability Ω, which is a random real, and holds an infinite amount of information. Ω, then, is an oracle for the halting problem. This quantity requires infinitely many bits to represent on any medium (essentially it is incompressible), and there is no effective procedure to calculate it. A hypercomputer must, however, hypercompute Omega by some other means than effective computation. For ordinary discrete computers, there is an approximation procedure from below that will approximate Omega using a simple time-sharing program. However, the program can never know, at any given instant, how close it is to Ω.

Theoretical possibilities for a hypercomputer

• A quantum mechanical system which somehow uses (for example) an infinite superposition of states to compute a non-recursive function¹. Such a system could not be an ordinary qubit quantum computer because it has been proved that regular quantum computers are Turing reducible.
• A Turing machine which can complete infinitely many steps and has infinite storage space.³ (see supertask)
• A non-deterministic Turing machine which has a preference ordering over its final states.
• 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.

At this stage, none of these devices seem physically plausible, and so hypercomputers are likely to remain a mathematical model for embodying super-Turing computation.

See also

• The Church-Turing thesis

Notes

1. There have been some claims to this effect; see Tien Kieu, Quantum Algorithm for Hilbert's Tenth Problem : [1]. & the ensuing literature. Errors have been pointed out in Kieu's paper (cf. [4]) 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".
2. See her monograph Neural Networks and Analog Computation: Beyond the Turing Limit [5], and for a critical discussion, Keith Douglas' M.S. thesis, Super-Turing Computation: a Case Study Analysis [6].
3. Simply being able to run for an unbounded number of steps (forever, i.e. potential infinity) does not suffice. On the other hand, notion of computation in the limit does. If we consider again the approximation procedure for Omega, this is a very slowly monotonically converging approximation. While every number in the series of approximation is computable, the limit Ω is not. If the device can realize all of these infinitely many approximation steps, and obtains directly Omega, and stores it in its infinite extent, then it can easily solve the halting problem.

References

1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
2. Tien Kieu, Quantum Algorithm for the Hilbert's Tenth Problem, Int. J. Theor. Phys., 42 (2003) 1461-1478, e-print archive quant-ph/0110136 (PDF)
3. Toby Ord, Hypercomputation: computing more than the Turing machine (PDF), Honours Thesis, University of Melbourne, 2002.
4. Boris Tsirelson. The quantum algorithm of Kieu does not solve the Hilbert's tenth problem. e-print archive quant-ph/0111009 (PDF)
5. Tien Kieu, Reply to "The quantum algorithm of Kieu does not solve the Hilbert's tenth problem". e-print archive quant-ph/0111020 (PDF)
6. Hava Siegelman. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
7. Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
8. 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.