Turing complete

From Wikipedia, the free encyclopedia
(Redirected from Turing completeness)
Jump to: navigation, search

A computer is Turing complete if it can solve any problem that a Turing machine can, given an appropriate algorithm and the necessary time and memory. When applied to a programming language, this phrase means that it can fully exploit the capabilities of a Turing complete computer.

Actual computers have to operate on limited memory and are not Turing complete in the mathematical sense. If they can run any program they are equivalent to linear bounded automata, a weaker theoretical machine. Informally, however, calling a computer Turing complete means that it can execute any algorithm.

The ability to run any algorithm is a necessary condition for a computer to be called Turing complete. For this reason, a basic calculator is not Turing complete and neither is a scientific calculator that only evaluates specific functions.