Turing Completeness

Turing Completeness

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine. A classic example is the lambda calculus. The concept is named after Alan Turing.

Computability theory includes the closely related concept of Turing equivalence. Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P. Thus, a Turing-complete system is one that can simulate a Turing machine; and, per the Church-Turing thesis, that any real-world computer can be simulated by a Turing machine, it is Turing equivalent to a Turing machine.

In colloquial usage, the terms "Turing complete" or "Turing equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate any other real-world general-purpose computer or computer language, within the bounds of finite memory – they are linear bounded automaton complete. A universal computer is defined as a device with a Turing complete instruction set, infinite memory, and an infinite lifespan; all general purpose programming languages and modern machine instruction sets are Turing complete, apart from having finite memory.

In practice, Turing completeness means that rules followed in sequence on arbitrary data can produce the result of any calculation. In imperative languages, this can be satisfied by having, at a minimum, conditional branching (e.g., an "if" and "goto" statement) and the ability to change arbitrary memory locations (e.g., having variables). To show that something is Turing complete, it is enough to show that it can be used to simulate the most primitive computer, since even the simplest computer can be used to simulate the most complicated one.