Hypercomputation

(Redirected from Hypercomputer)

Categories: Computability

Hypercomputation refers to methods for the computation of non-Turing-computable functions. A similar used term is super-Turing computation but hypercomputation has an additional sense of believing that such device is 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.

People usually think that hypercomputation was first introduced by Alan Turing; most of them misunderstand the sense of Turing´s work in his 1939 paper Systems of logic based on ordinals, which investigated mathematical systems in which an oracle was available to compute a single arbitrary (non-recursive) function from naturals to naturals in order to proof that even in those more powerful systems undecidability is present.

Other kinds of hypercomputer include:

  • A quantum mechanical system which somehow uses (for example) an infinite superposition of states to compute a non-recursive function1. Such a system could not be an ordinary qubit quantum computer because it was proved that is Turing reducible.
  • A Turing machine which runs for an infinite period of time or infinite space.
  • A Turing machine which increases its speed exponentially over time. In a Newtonian universe, such a gadget might operate by manufacturing a clone of itself which was only half the size and operated at twice the speed (similar to Thomson's lamp, 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.

[edit]

See also

[edit]

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].
[edit]

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.