Hypercomputation

From Wiki @ Karl Jones dot com
Revision as of 07:13, 22 September 2016 by Karl Jones (Talk | contribs)

Jump to: navigation, search

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

External links