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 numbers 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

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.