Turing Completeness

Turing completeness is a concept from computability theory that defines the power of a computational system. It originates from Alan Turing’s 1936 paper describing a theoretical device known as the Turing machine. This machine consists of an infinitely long tape, a head that can read, write, and move along the tape, and a set of states and transition rules. Despite its simplicity, a Turing machine can perform any computation that can be described algorithmically. A programming language or any other formal system is deemed ‘Turing complete’ if it has the capability to simulate a universal Turing machine. This implies that the language can compute anything that is computable.

The core requirements for a system to be Turing complete are conditional branching (e.g., if-then-else statements) and the ability to loop indefinitely or recursively (e.g., while, for loops). These constructs allow the system to make decisions and repeat operations, which is sufficient to model the behavior of a Turing machine’s state transitions and tape manipulation. The Church-Turing thesis, a fundamental principle in computer science, posits that any function that is naturally considered ‘computable’ can be computed by a Turing machine. Therefore, a Turing-complete language is, in theory, capable of expressing any algorithm.

However, this theoretical power comes with a significant consequence: the halting problem. Turing proved that it is impossible to create a general algorithm that can determine, for all possible inputs, whether any given program will finish running or continue forever. This undecidability is an inherent property of all Turing-complete systems. For this reason, some domain-specific languages are intentionally designed to be non-Turing complete. For example, standard SQL and HTML are not Turing complete, which guarantees that their scripts or definitions will terminate and prevents them from entering accidental infinite loops, a desirable property for database queries and document rendering.