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 17 hours by pinc