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 demostrate that it can fully exploit the capabilities of a turing complete computer.

Being Turing complete does not have to do with efficiency, that is the time and memory required to run algorithms. For example, all tablets, personal computers, and servers that use x86 or x86-64 processors are Turing complete but their efficiency in running algorithms varies greatly. However, since they are using the same computer architecture only time can vary, not memory requirements.

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