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