Super-Turing computation
|
|
Super-Turing computation is any form of computation that cannot be performed by a Turing machine. This includes, but is not limited to:
- Solving problems that can be solved on a Turing machine, in a lower time complexity class than they can be solved in on a Turing machine.
- Solving an uncountable number of problems simultaneously.
- Working with irrational values with the same efficiency that a finite Turing machine works with rational numbers.
No physical examples of Super-Turing computers are currently known. Classes of computers that might have Super-Turing capabilities in some physical models include:
- Pulse computers
- Analog computers
- Quantum computers
- Digital computers (in a suitably constructed spacetime)
Difference between super-Turing computation and Hypercomputation
Super-Turing computation is any form of information processing that a Turing machine cannot do. There are no restrictions on the class of super-Turing machines beyond this. Hypercomputation is a sub-class of super-Turing computation, which is able to compute non-computable functions, i.e. functions that cannot be computed by Turing machines. In other words, not all super-Turing machines are Hypercomputers, but all Hypercomputers are super-Turing machines. For example, a machine that can solve the Traveling Salesman Problem in constant time is a super-Turing machine but not a Hypercomputer.
An example of a putative Super-Turing computation which is not a hypercomputation in this sense would be one of Hava Siegelman's neural networks; these have the ability to recognize nonrecursive languages, but there is no clear method by which they can compute more general non-recursive functions (i.e. not two-valued).
Another example might be an alternating or non-deterministic Turing machine; under the (as yet unproven) hypothesis that P≠NP, these produce super-Turing computation because they have a larger class of polynomial time functions; but they are not hypercomputers because they cannot compute anything nonrecursive.
External links
- http://www.nature.com/nsu/010329/010329-8.html (cached: [1] (http://64.233.167.104/search?q=cache:jIbZkv6OfqIJ:www.nature.com/nsu/010329/010329-8.html+%22liquid+logic%22&hl=en&ie=UTF-8) )
- the Liquid Computer A Novel Strategy for Real-Time Computing on Time Series (http://www.lsm.tugraz.at/papers/lsm-telematik.pdf)
- On the computational power of neural nets (ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z)
- Computational complexity of real valued recursive functions and analog circuits. (http://math.isa.utl.pt/~mlc/phdthesis.ps)
- The simple dynamics of super Turing theories (http://dx.doi.org/doi:10.1016/S0304-3975(96)00087-4)