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:

• 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 functions. In other words, not all super-Turing machines are Hypercomputers, but all Hypercomputers are super-Turing machines.

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] )
• the Liquid Computer A Novel Strategy for Real-Time Computing on Time Series
• On the computational power of neural nets
• Computational complexity of real valued recursive functions and analog circuits.
• The simple dynamics of super Turing theories