Difference between revisions of "Hypercomputation"

Revision as of 07:11, 22 September 2016

Hypercomputation or super-Turing computation refers to models of computation that can provide outputs that are not Turing computable.

Description

For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that can correctly evaluate every statement in Peano arithmetic.

The Church–Turing thesis states that any "effectively 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 effectively computable in the Church-Turing sense.

Technically the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses instead on the computation of useful, rather than random, uncomputable functions.

See also

• Computation
• Digital physics
• Supertask

External links

• Hypercomputation @ Wikipedia