Difference between revisions of "Hypercomputation"
Karl Jones (Talk | contribs) |
Karl Jones (Talk | contribs) |
||
| Line 3: | Line 3: | ||
== Description == | == 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]]. | + | 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 axioms|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. | 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 | + | 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 == | == See also == | ||
| Line 17: | Line 17: | ||
* [[Entscheidungsproblem]] | * [[Entscheidungsproblem]] | ||
* [[Halting problem]] | * [[Halting problem]] | ||
| + | * [[Peano axioms]] | ||
| + | * [[Probabilistic Turing machine]] | ||
* [[Supertask]] | * [[Supertask]] | ||
Latest revision as of 07:18, 22 September 2016
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
