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 exploits 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.

Any well-known computer that can run arbitrary algorithms is Turing complete. This makes any calculator, basic or scientific, that can only evaluate expressions from a given set of functions and operations non-turing complete.