Difference between revisions of "Hypercomputation"
Karl Jones (Talk | contribs) (Created page with "'''Hypercomputation''' or '''super-Turing computation''' refers to models of computation that can provide outputs that are not Turing computable. == Description == For examp...") |
Karl Jones (Talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | '''Hypercomputation''' or '''super-Turing computation''' refers to models of computation that can provide outputs that are not Turing computable. | + | '''Hypercomputation''' or '''super-Turing computation''' refers to models of computation that can provide outputs that are not [[Computable function|Turing computable]]. |
== Description == | == 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]]. | + | 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. | + | 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. | 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. | ||
| Line 11: | Line 11: | ||
== See also == | == See also == | ||
| + | * [[Church–Turing thesis]] | ||
| + | * [[Computable function]] | ||
* [[Computation]] | * [[Computation]] | ||
* [[Digital physics]] | * [[Digital physics]] | ||
| + | * [[Entscheidungsproblem]] | ||
| + | * [[Halting problem]] | ||
* [[Supertask]] | * [[Supertask]] | ||
Revision as of 07:13, 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 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
- Hypercomputation @ Wikipedia
