Hypercomputation

From Wiki @ Karl Jones dot com
Revision as of 07:11, 22 September 2016 by Karl Jones (Talk | contribs) (Created page with "'''Hypercomputation''' or '''super-Turing computation''' refers to models of computation that can provide outputs that are not Turing computable. == Description == For examp...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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