Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Hypercomputation
Main Page | See live article | Alphabetical index

Hypercomputation

Hypercomputation is the theory of methods for the computation of non-recursive functions. The classes of functions which they can compute is studied in the field known as recursion theory. A similar recent term is super-Turing computation, which has been used in the neural network literature to describe machines with various expanded abilities, possibly including the ability to compute directly on real numbers, the ability to carry out uncountably many computations simultaneously, or the ability to carry out computations with exponentially lower complexity than standard Turing machines.

Hypercomputation was first introduced by Alan Turing 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 naturalss to naturals.

Other posited kinds of hypercomputer include:

At this stage, none of these devices seem physically plausible, and so hypercomputers are likely to remain a mathematical fiction.

Table of contents
1 See also

See also

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

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)