In computability theory, a system of data-manipulation rules is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine.
This means that this system is able to recognize or decide other data-manipulation rule sets.
Turing completeness is used as a way to express the power of such a data-manipulation rule set.
Virtually all programming languages today are Turing-complete.
The concept is named after English mathematician and computer scientist Alan Turing.
To show that something is Turing-complete, it is enough to show that it can be used to simulate some Turing-complete system.
For example, an imperative language is Turing-complete if it has conditional branching and the ability to change an arbitrary amount of memory.
Of course, no physical system can have infinite memory; but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete.
Last Updated on 2 years by pinc