Super-Turing computation - Definition and Overview

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:

• Pulse computers
• Analog computers
• Quantum computers

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)