View source for Hypercomputation

'''Hypercomputation''' or '''super-Turing computation''' refers to models of computation that can provide outputs that are not [[Computable function|Turing computable]].

== Description ==

For example, a machine that could solve the [[halting problem]] would be a hypercomputer; so too would one that can [[Entscheidungsproblem|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 ==

* [[Church–Turing thesis]]
* [[Computable function]]
* [[Computation]]
* [[Digital physics]]
* [[Entscheidungsproblem]]
* [[Halting problem]]
* [[Supertask]]

== External links ==

* [https://en.wikipedia.org/wiki/Hypercomputation Hypercomputation] @ Wikipedia

[[Category:Computation]]