Hypercomputation
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 probabilistic 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
- Peano axioms
- Probabilistic Turing machine
- Supertask
External links
- Hypercomputation @ Wikipedia
