Hypercomputation

Hypercomputation or super-Turing computation is a set of hypothetical

The Church–Turing thesis states that any "computable" function that can be computed by a mathematician with a pen and paper using a finite set of simple algorithms, can be computed by a Turing machine. Hypercomputers compute functions that a Turing machine cannot and which are, hence, not computable in the Church–Turing sense.

Technically, the output of a

A computational model going beyond Turing machines was introduced by Alan Turing in his 1938 PhD dissertation Systems of Logic Based on Ordinals.^[1] This paper investigated mathematical systems in which an oracle was available, which could compute a single arbitrary (non-recursive) function from naturals to naturals. He used this device to prove that even in those more powerful systems, undecidability is still present. Turing's oracle machines are mathematical abstractions, and are not physically realizable.^[2]

State space

In a sense, most functions are uncomputable: there are ${\displaystyle \aleph _{0}}$ computable functions, but there are an

${\displaystyle 2^{\aleph _{0}}}$

Models

Hypercomputer models range from useful but probably unrealizable (such as Turing's original oracle machines), to less-useful random-function generators that are more plausibly "realizable" (such as a

Uncomputable inputs or black-box components

This section is in prose. You can help by converting this section, if appropriate. Editing help is available. (July 2023)

A system granted knowledge of the uncomputable, oracular Chaitin's constant (a number with an infinite sequence of digits that encode the solution to the halting problem) as an input can solve a large number of useful undecidable problems; a system granted an uncomputable random-number generator as an input can create random uncomputable functions, but is generally not believed to be able to meaningfully solve "useful" uncomputable functions such as the halting problem. There are an unlimited number of different types of conceivable hypercomputers, including:

• Turing's original oracle machines, defined by Turing in 1939.
• A
  real computer (a sort of idealized analog computer) can perform hypercomputation^[4] if physics admits general real variables (not just computable reals), and these are in some way "harnessable" for useful (rather than random) 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 require the ability to measure the real-valued physical value to arbitrary precision, though standard physics makes such arbitrary-precision measurements theoretically infeasible.^[5]
  • Similarly, a neural net that somehow had Chaitin's constant exactly embedded in its weight function would be able to solve the halting problem,[6] but is subject to the same physical difficulties as other models of hypercomputation based on real computation.
• Certain fuzzy logic-based "fuzzy Turing machines" can, by definition, accidentally solve the halting problem, but only because their ability to solve the halting problem is indirectly assumed in the specification of the machine; this tends to be viewed as a "bug" in the original specification of the machines.^[7][8]
  • Similarly, a proposed model known as
    fair nondeterminism can accidentally allow the oracular computation of noncomputable functions, because some such systems, by definition, have the oracular ability to identify reject inputs that would "unfairly" cause a subsystem to run forever.^[9][10]
• Dmytro Taranovsky has proposed a finitistic model of traditionally non-finitistic branches of analysis, built around a Turing machine equipped with a rapidly increasing function as its oracle. By this and more complicated models he was able to give an interpretation of second-order arithmetic. These models require an uncomputable input, such as a physical event-generating process where the interval between events grows at an uncomputably large rate.^[11]
  • Similarly, one unorthodox interpretation of a model of unbounded nondeterminism posits, by definition, that the length of time required for an "Actor" to settle is fundamentally unknowable, and therefore it cannot be proven, within the model, that it does not take an uncomputably long period of time.^[12]

"Infinite computational steps" models

In order to work correctly, certain computations by the machines below literally require infinite, rather than merely unlimited but finite, physical space and resources; in contrast, with a Turing machine, any given computation that halts will require only finite physical space and resources.

A Turing machine that can complete infinitely many steps in finite time, a feat known as a

It seems natural that the possibility of time travel (existence of closed timelike curves (CTCs)) makes hypercomputation possible by itself. However, this is not so since a CTC does not provide (by itself) the unbounded amount of storage that an infinite computation would require. Nevertheless, there are spacetimes in which the CTC region can be used for relativistic hypercomputation.^[14] According to a 1992 paper,^[15] a computer operating in a Malament–Hogarth spacetime or in orbit around a rotating black hole^[16] could theoretically perform non-Turing computations for an observer inside the black hole.^[17][18] Access to a CTC may allow the rapid solution to PSPACE-complete problems, a complexity class which, while Turing-decidable, is generally considered computationally intractable.^[19][20]

Quantum models

Some scholars conjecture that a

containing ${\displaystyle \Sigma _{1}^{0}}$ or ${\displaystyle \Pi _{1}^{0}}$. Limiting-recursion, by contrast, can compute any predicate or function in the corresponding

${\displaystyle \Delta _{2}^{0}}$

${\displaystyle \Sigma _{2}^{0}}$

Model	Computable predicates	Notes	Refs
supertasking	${\displaystyle \operatorname {tt} \left(\Sigma _{1}^{0},\Pi _{1}^{0}\right)}$	dependent on outside observer	[28]
limiting/trial-and-error	${\displaystyle \Delta _{2}^{0}}$		[23]
iterated limiting (k times)	${\displaystyle \Delta _{k+1}^{0}}$		[25]
Blum–Shub–Smale machine		incomparable with traditional computable real functions	[29]
Malament–Hogarth spacetime	HYP	dependent on spacetime structure	[30]
analog recurrent neural network	${\displaystyle \Delta _{1}^{0}[f]}$	f is an advice function giving connection weights; size is bounded by runtime	[31][32]
infinite time Turing machine	${\displaystyle AQI}$	Arithmetical Quasi-Inductive sets	[33]
classical fuzzy Turing machine	${\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}}$	for any computable t-norm	[8]
increasing function oracle	${\displaystyle \Delta _{1}^{1}}$	for the one-sequence model; ${\displaystyle \Pi _{1}^{1}}$ are r.e.	[11]

Criticism

Martin Davis, in his writings on hypercomputation,^[34][35] refers to this subject as "a myth" and offers counter-arguments to the physical realizability of hypercomputation. As for its theory, he argues against the claims that this is a new field founded in the 1990s. This point of view relies on the history of computability theory (degrees of unsolvability, computability over functions, real numbers and ordinals), as also mentioned above. In his argument, he makes a remark that all of hypercomputation is little more than: "if non-computable inputs are permitted, then non-computable outputs are attainable."^[36]

See also

• Digital physics
• Limits of computation

References