Hypercomputation

Hypercomputation refers to methods for the computation of non-computable functions. The field known as computability theory studies the classes of functions which can be computed through these, and other, methods. 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 higher complexity than standard Turing machines.

Related Topics:
Non-computable function - Computability theory - Super-Turing computation - Neural network - Real number - Uncountably - Exponential - Complexity - Turing machine

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Alan Turing - Oracle - Natural

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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¹. Such a system could not be an ordinary qubit quantum computer.
• A Turing machine which runs for an infinite period of time (that is, a Zeno machine).
• 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 Thompson'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 fiction. Moreover, the most physically plausible methods proposed do not gracefully degrade. A "real computer" described by Hava Siegelmann degrades to a sub-Turing computer in the presence of many sorts of noise 2. Digital physics is the other extreme from hypercomputation, in that it assumes that physical processes are not only harnessable, but are themselves computable.

Related Topics:
2 - Digital physics

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

 
Hypercomputation: See also ►