Turing completeness

In computability theory, a 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 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 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 .

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 can have infinite memory; but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete.