Super-Turing computation
Super-Turing computation is any form of computation that cannot be performed by a finite 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:
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 meets a further set of mathematical restrictions. In other words,
- not all super-Turing machines are Hypercomputers, but
- all Hypercomputers are super-Turing machines.
Thus, if a given property does not belong to the class of Hypercomputers, that does not imply that it does not belong to a given instance in the class of super-Turing computers. (see Venn diagram)
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)