The basic idea
A programming language is called Turing complete if, given enough time and memory, it can carry out any computation that any other general-purpose computing system can carry out. The name comes from Alan Turing, who studied what it means to compute something using an idealized machine.
The claim is easy to misread. It is not about speed, convenience or whether the language is pleasant. It says only that the language is not missing any fundamental ability. A Turing complete language is, in principle, as capable as any other.
What a language needs
Different Turing complete languages look very different, but they tend to share a few ingredients:
- Some form of memory that can grow without limit. The language must be able to store as much information as a task requires, at least in theory.
- A way to read and change that memory. It must be able to remember results and use them later.
- Conditional behavior. The program must be able to choose what to do next based on what is stored.
- Repetition. It needs loops or an equivalent, such as recursion or a jump back to an earlier point, so it can keep working for as long as the task requires.
With just these four things, a surprising amount is possible. Arithmetic, comparison, searching and sorting can all be built up from small pieces. The set of instructions can be very small indeed, as long as these abilities are present.
An example from a small language
Consider the Brainfuck commands. With a row of cells, commands to change the current cell, and a loop that repeats while a cell is nonzero, the language has memory, a way to change it, a test and repetition. Those are the same four ingredients. Despite having only eight commands, the language is generally regarded as Turing complete, provided its tape is treated as unlimited.
The same reasoning applies to other minimal designs. Tag systems and counter machines are tiny abstract systems that have been shown to be capable of full computation. Their value is in showing that the ingredients really are enough.
Why “unbounded memory” is the catch
The words “given enough memory” carry a lot of weight. No physical computer has unlimited memory, so strictly speaking no real machine is Turing complete. When people call a language Turing complete, they mean the language itself puts no ceiling on memory, even if any real machine running it eventually runs out.
This is the difference between a language and a machine, and it is explored further under infinite memory. A system with a fixed, finite amount of storage can only be in a limited number of states, which puts it in the class of finite automata. These are powerful for some tasks, such as checking whether text matches a pattern, but they cannot do everything a full programming language can.
Surprising places it shows up
Turing completeness is not limited to things designed as programming languages. Some systems turn out to be complete almost by accident:
- Cellular automata. Rule 110, a one-dimensional pattern of cells updated by a simple local rule, is known to be capable of universal computation. The Game of Life, a grid with a handful of rules about neighbors, is also known to be Turing complete.
- Rewriting systems, where text is transformed by rules.
- Some games and spreadsheet-like systems.
The usual way to establish this is to show that the system can imitate a machine already known to be complete. That technique is the subject of the completeness proof approach: if your new system can simulate a known universal one, it must be universal too.
What it does not tell you
It is easy to attach meaning to the term that is not there. Some points worth keeping straight:
- It does not mean the language is practical. A Turing complete language can be so awkward that no one wants to use it for real work.
- It does not mean it is fast. Two complete languages can differ enormously in how long the same job takes.
- It does not mean it can solve every problem. Some questions cannot be answered by any program at all, however powerful the language. The halting problem, which asks whether an arbitrary program will ever finish, is the classic example.
- It is not a rating. A language is either capable of universal computation or it is not. There is no “more complete.”
The link to the Church-Turing thesis
Why do we trust that “anything computable” is a meaningful category? The answer is an idea called the Church-Turing thesis. It says that the intuitive notion of an effective, step-by-step procedure matches what Turing machines can compute. This is not a theorem that can be proven, because it connects a mathematical definition to an informal notion, but it is widely accepted, partly because many independently developed models of computation turned out to be equivalent. A Turing machine is the most common reference point, which is why the term is named after it.
Why it matters for esoteric languages
For designers of unusual languages, Turing completeness works as a kind of entry ticket. If a quirky new language is complete, it is a serious computational system, however odd. If it is not, it is more limited, which can be interesting in its own right. Many hobby languages announce their status early for this reason.
Whether a particular language is complete is not always obvious. The case of the Befunge language, for instance, depends on details of how much space and memory the version allows, and the question of Befunge completeness is a topic of its own.
A practical way to think about it
Turing completeness is best viewed as a floor, not a ceiling. It marks the point where a language has enough machinery to do any computation, and everything beyond that point, including readability, speed and safety, is a matter of design. The broader field of computability theory explores what lies on either side of that floor and which problems no program can solve at all.