hypercomputation
Sign in to saveAlso known as hypercomputer, super-Turing computation
Hypercomputation or super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that could correctly evaluate every statement in Peano arithmetic.
~13 min read
Encyclopedic overview
12 sectionsContents
- History
- State space
- Models
- Uncomputable inputs or black-box components
- "Infinite computational steps" models
- Quantum models
- "Eventually correct" systems
- Analysis of capabilities
- Criticism
- See also
- References
- Further reading
Hypercomputation or super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that could correctly evaluate every statement in Peano arithmetic.
The Church–Turing thesis states that any "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 computable in the Church–Turing sense.
Excerpted from Wikipedia’s “hypercomputation” article, available under the CC BY-SA 4.0 licence.