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.
Wikidata facts
Show 1 more fact
- Stack Exchange tag
- cstheory.stackexchange.com/tags/hypercomputation
Sources (1)
via Wikidata · CC0
~13 min read
Article
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.