Hypercomputation

From Free net 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, as limits or integrations.

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

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).

The challenge of hypercomputation

Today, algorithmic information theory helps us understand better what is required for hypercomputation. 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 <math>\Omega</math>, which is a random real, and holds an infinite amount of information. <math>\Omega</math>, 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, obtain Omega by some other means than familiar Turing 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 and conceptual possibilities for a hypercomputer

• A discrete computer that has access to the halting probability <math>\Omega</math> can solve the halting problem. For an n-bit input program, the first n bits of <math>\Omega</math> are read, which gives the number of halting programs <math>k</math> among all <math>2^n</math> programs. Then, we timeshare all candidate programs with a simple watchguard policy. At step <math>i</math>, we run each candidate program for <math>i</math> steps. This iteration continues until <math>k</math> programs terminate, and we have all n-bit programs that terminate. Then, we simply check if the input program is among these <math>k</math> programs.
• A Turing machine that can complete infinitely many steps.¹ (see supertask)
• 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-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 (they may yield speedup for some problems, but they don't allow solving new problems).
• A digital computer in a specially constructed spacetime, which enables it to 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.

See also

• The Church-Turing thesis

Notes

1. 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 <math>\Omega</math> 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.
2. There have been some claims to this effect; see Tien Kieu, Quantum Algorithm for Hilbert's Tenth Problem : [2]. & the ensuing literature. Errors have been pointed out in Kieu's paper (cf. [3]) 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". [4]

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. Boris Tsirelson. The quantum algorithm of Kieu does not solve the Hilbert's tenth problem. e-print archive quant-ph/0111009 (PDF)
4. Tien Kieu, Reply to "The quantum algorithm of Kieu does not solve the Hilbert's tenth problem". e-print archive quant-ph/0111020 (PDF)
5. Hava Siegelman. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
6. 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)
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.
9. Thomas Natschläger et al. the "Liquid Computer": A Novel Strategy for Real-Time Computing on Time Series
10. http://www.nature.com/nsu/010329/010329-8.html A Nature article on the above.
11. On the computational power of neural nets