Home > Hypercomputation

Hypercomputation is the law of methods for the computation of non-computable functions. The classes of functions which they can compute is studied in the field known as computability 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 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 ¹ . Such a system could not be an ordinary qubit quantum computer.
• A Turing machine which runs for an infinite period of time.
• 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 supertaskIn mathematics and philosophy, a supertask is a task involving an infinite number of steps, completed in a finite amount of time. The term supertask was coined by the philosopher J. Examples of supertasks: Thompson's lamp a lamp can be either on or off.).
• A non-deterministic Turing machineIn theoretical computer science, an ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s', q', d), where s' is the symbol to be written by the head, q which has a preference ordering over its final states.
• A " real computer" (a sort of idealized analog computerAn analog computer ( American English) or analogue computer ( British English) is a form of computer using electronic or mechanical phenomena to model the problem being solved by using one kind of physical quantity to represent another. The term is used i) might be able to perform hypercomputation if physics admits general real variables (not just computable realsIn mathematics, theoretical computer science and mathematical logic, the computable numbers also known as the recursive numbers are the subset of the real numbers consisting of the numbers which can be computed by a finite, terminating algorithm. They can), 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 constantIn the computer science subfield of algorithmic information theory the Chaitin constant or halting probability is a construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or progr), and would at minimum require the ability to measure a real-valued physical value to arbitrary precision despite thermal noiseIn telecommunication or other systems, thermal noise Johnson noise is the noise generated by thermal agitation of electrons in a conductor. The noise power, P , in watts, is given by P 4kT Δf , where k is Boltzmann's constant in joules per kelvin, T 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 ² . Digital physics is the other extreme from hypercomputation, in that it assumes that physical processes are not only harnessable, but are themselves computable.