Turing complete

From Wikipedia, the free encyclopedia
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. This terminology can be also applied to a programming language, to demonstrate 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 execute arbitrary algorithms 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.