The core idea
To show that a language is Turing complete, you show that it can do everything a Turing machine can do. You do not need to enumerate every possible program. Instead you use a shortcut: take a system already known to be universal, and show that your language can simulate it. If your language can imitate that system step for step, then your language can compute anything the system can, and therefore anything computable.
This works because simulation is transitive. If system A can simulate every Turing machine, and your language L can simulate A, then L can simulate every Turing machine. The whole proof reduces to building one faithful simulation.
Step 1: choose a good target
The easiest choice is a system whose parts map neatly onto your language’s features. Common targets include:
- A Turing machine, which is the most direct but requires a tape with a movable head and a state table.
- A counter machine with two counters, which only needs increment, decrement and a test for zero, plus a small set of numbered instructions.
- A tag system or another rewriting system, when your language handles text or queues well.
- Another esoteric language already known to be universal, such as Brainfuck, whose few Brainfuck commands are easy to map onto many designs.
Picking a minimal target keeps the proof short. A two-counter machine is popular because only two kinds of operations need to be implemented. If your language has a stack, remember that two stacks can imitate a tape, and that is another well-trodden route.
Step 2: represent the target’s memory
Next, decide how the simulated data lives inside your language. For a counter, this might be an integer stored in a cell, or the height of a stack, or the position of a marker. For a tape, it might be a pair of stacks holding the cells to the left and right of the head, or a row of cells in a grid.
This is where the question of unbounded memory enters. A Turing machine’s tape is unlimited. Your language must be able to grow its storage without a fixed ceiling, at least in the idealized sense, or the simulation will break down once the simulated tape gets too long. If the language’s real implementation limits integers or grid size, you usually state the result as holding for an idealized version of the language with those limits removed, and say so openly.
Step 3: represent the target’s control
The simulated machine has a finite program: a list of states or numbered instructions. Your language must mirror this. Typically one block of code corresponds to each simulated instruction, and the language’s own control flow plays the role of the simulated “current state.”
For a grid language, that often means laying out a region for each instruction and routing the instruction pointer between regions based on the data, which relates to conditional branching and the way the pointer travels around the grid. For a language with no explicit jumps, you may encode the state as data and write a dispatch loop that looks at it.
Step 4: show that each step is faithful
For each kind of operation in the target system, show that your language performs the matching change. For a two-counter machine, you would argue that:
- incrementing a counter in the target adds one to the matching representation;
- decrementing does the opposite, and the test for zero gives the right answer;
- after each operation, control moves to the right next instruction.
The argument is usually an induction: if the representation matches the target’s configuration before a step, it matches after. You also need to cover what happens when the target halts, so that the simulation halts in the corresponding way.
Step 5: be honest about the loose ends
Many informal completeness claims quietly skip one of the following:
- Bounded memory in real implementations, where the gap between infinite memory and physical hardware needs a sentence of honesty.
- Input and output. The simulation should not require interaction the language lacks.
- Whether the encoding itself does any hidden computation. If your translation of the target machine already requires solving hard problems, the proof is cheating. The translation should be simple and mechanical.
This last point matters. A mapping that is too powerful could “prove” anything, so a reasonable proof keeps the encoding clearly weaker than the thing being simulated.
A short example of the reasoning
Suppose a language has an unbounded queue and a way to branch on the front element. A tag system repeatedly removes some symbols from the front of a string and appends a replacement to the end, depending on the first symbol. A queue does exactly that, so each production maps to a short branch that pops and pushes. Because certain tag systems are known to be universal, the language is universal too, under the assumption of an unbounded queue. The proof is short because the target and the language fit each other.
What a proof does not tell you
Turing completeness is a statement about what is possible, not what is pleasant or efficient. A proof can involve a simulation that runs absurdly slowly or needs awkward encodings. The word is easy to overuse, and the idea behind Turing completeness is a statement about possibility only. The proof is also a translation in spirit: every step of the known system gets a matching piece in the new language.