The Super-Turing computation reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

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

See also: hypercomputation

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)

Web references

http://www.nature.com/nsu/010329/010329-8.html (cached: [1] )

http://www.lsm.tugraz.at/papers/lsm-telematik.pdf

ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z

http://math.isa.utl.pt/~mlc/phdthesis.ps

This is the "Super-Turing computation" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.