Encyclopedia > Hypercomputation

  Article Content


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.

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 naturals to naturals.

Other posited kinds of hypercomputer include:

  • A quantum mechanical system which somehow uses (for example) an infinite superposition of states to compute a non-recursive function.
  • A Turing machine which is running for an infinite period of time (perhaps the observer is being dropped into a black hole).
  • A Turing machine which is accelerating exponentially (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).
  • A non-deterministic Turing machine which has a preference ordering over its final states.
  • An analog computer might be able to perform hypercomputation if physics admits real variables (not just computable reals), and these are in some way "harnessable" for computation. This might require quite outlandish laws of physics (for example, a measurable physical constant with the value Ω).

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

See also: the Church-Turing thesis.


  1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc. 45, 1939

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Weed control

... during the early stages of growth when each plant can find the resources it requires without interfering with the others. However as the seedlings’ size increases, thei ...