Turing completeness

Any system of data-manipulation rules is said to be Turing-complete if it can be used to simulate any Turing machine (devised by English mathematician and computer scientist Alan Turing). This means that this system can recognize and decode other data manipulation rule sets, allowing it to be used to solve any computational problem.

In terms of programming languages, such a language has to have the following properties:

• Support for arithmetic operations of addition, subtraction, multiplication, and division
• Has the ability to make decisions based on what it sees in memory, meaning it can make a choice based on its inputs by using conditional statements
• Can perform loops, supports return statements, and is able to run forever if physical resources are available
• Has the ability to use infinite memory if it were physically possible
• Has random access memory, meaning that the language can access any part of this type of memory directly and quickly.

Turing completeness is used to express the power of a programming language. The programming languages in use today are, in most cases, Turing-complete.