Adding a Stack, Then a Tape

The previous lesson showed that a finite automaton fails whenever the input demands an unbounded count. The narrowest possible repair is to attach a stack: the machine may push a symbol, pop a symbol, or leave the stack alone on each move, and it may read only the top.

That is a pushdown automaton, and it is exactly enough for balanced brackets. Push on every opening bracket, pop on every closing one, accept if the stack is empty at the end. The depth is now held in the stack rather than in the state set, so nothing is capped in advance.

The languages recognised this way are the context-free languages, the same class the context-free grammars generate. The lesson Formal Grammars and the Chomsky Hierarchy approaches this ladder from the grammar side and asks where human language sits on it.

A stack is a strictly disciplined memory: the only thing readable is the top, and reaching what is underneath destroys everything above it. That discipline has a price.

Take a^n b^n c^n, equal runs of three symbols. Counting the a's against the b's consumes the stack, and by the time the c's arrive the count is gone. No pushdown automaton recognises it.

The formal instrument is the pumping lemma for context-free languages, proved by Bar-Hillel, Perles and Shamir in 1961. It says every sufficiently long string in a context-free language can be split so that two of its interior pieces may be repeated together any number of times and stay in the language. For a^n b^n c^n any such pair of pieces touches at most two of the three symbols, so repeating them breaks the equality and produces a string that must be rejected.

The stack failed not because it was small but because it was ordered. So remove the ordering. Give the machine a tape divided into cells, a head that can read and write one cell, and moves that shift the head left or right by one. The tape is unbounded: it never runs out.

That is a Turing machine, introduced by Alan Turing in "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, series 2, volume 42, pages 230 to 265.

Nothing here is fast. The head moves one cell at a time, so reaching a distant cell costs a step per cell. What changed is not speed but reach: any cell can be revisited, in any order, as many times as wanted. a^n b^n c^n becomes routine, crossing off one a, one b and one c per pass.

A Turing machine is a table of rules, and simulating one takes a dozen lines. This machine accepts a^n b^n by repeatedly crossing off the leftmost a and the leftmost b.

# (state, symbol) -> (write, move, next_state)
RULES = {
    ("scan",  "a"): ("X", +1, "find_b"),   # claim an a
    ("scan",  "Y"): ("Y", +1, "scan"),
    ("scan",  "_"): ("_",  0, "accept"),   # nothing left, balanced
    ("find_b", "a"): ("a", +1, "find_b"),
    ("find_b", "Y"): ("Y", +1, "find_b"),
    ("find_b", "b"): ("Y", -1, "rewind"),  # pair it off
    ("rewind", "a"): ("a", -1, "rewind"),
    ("rewind", "Y"): ("Y", -1, "rewind"),
    ("rewind", "X"): ("X", +1, "scan"),    # back to the first unclaimed a
}

def run(tape, state="scan", head=0, budget=10_000):
    tape = list(tape) + ["_"] * 50
    for _ in range(budget):
        rule = RULES.get((state, tape[head]))
        if rule is None:
            return "reject"
        tape[head], move, state = rule[0], rule[1], rule[2]
        head += move
        if state == "accept":
            return "accept"
    return "no verdict within budget"

The budget is not part of the model. It is there because without it this function might never return, which is precisely the subject of the next lesson.

In the same year, working on the same problem, Alonzo Church published "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, volume 58, 1936, pages 345 to 363. His formalism, the lambda calculus, has no tape, no head and no states. It has variables, function definition and function application, and it computes by textual substitution.

The two systems could hardly look less alike. They turn out to define the same class of computable functions, and so does every other serious proposal that followed: general recursive functions, register machines, cellular automata.

That convergence is the evidence for the Church-Turing thesis: anything a human or machine could compute by a mechanical procedure is computable by a Turing machine. Note the word thesis. It is not a theorem and cannot be one, because "mechanical procedure" is an informal notion. It is an empirical claim that has survived ninety years of attempts to exceed it.

Each rung is bought with a specific relaxation, and each relaxation is the removal of one restriction on how memory may be accessed.

Finite states cap the total amount remembered. A stack lifts the cap but fixes the order of access. A tape lifts the ordering too, and at that point there is nothing left to relax: unbounded memory, arbitrary access, arbitrary rewriting.

That is why the ladder stops. Every further model anyone has proposed lands on the same rung rather than above it. The interesting consequence is the last box: once memory is no longer the binding constraint, the limits that remain must be of a completely different kind.

Turing's paper contains a second idea that matters as much as the machine. A Turing machine is a finite table of rules, so it can be written down as a string. And a string is something a Turing machine can read.

So there exists a universal machine U that takes as input a description of any machine M together with an input w, and simulates M on w. One fixed machine, capable of behaving like every other machine.

This is the theoretical statement of stored-program computing, and it is why an interpreter is possible, why a compiler can be written in the language it compiles, and why a CPU running different software is not a different CPU. It is also the hinge of the next lesson: because programs are data, a program can be handed a description of itself.

Because the ladder tops out, "Turing complete" is a much weaker compliment than it sounds. It says a system can express any computable function. It says nothing about whether doing so is efficient, safe or bearable.

The lambda calculus makes the point. It has three constructs and no data types, no loops, no numbers. Numbers and loops are encoded out of functions. It is Turing complete, and nobody would choose it as a systems language.

The reverse framing is more useful in practice. Some languages are Turing complete by accident, which means the questions in the next two lessons apply to them whether their designers wanted that or not. Others give up completeness on purpose, in exchange for guarantees that would otherwise be unavailable. Both are deliberate positions once you know where the line is.

The first two rows have a clean answer in the last column. The third does not, and that is the whole point.

The tape removed every memory constraint, so any impossibility that remains cannot be about storage. It has to be about something else. And there is a cost that arrived with the tape and has been quietly present since the simulator above: a finite automaton always halts, because it reads each symbol once and stops. A Turing machine has no such guarantee. It can loop forever.

The next lesson shows that this is not an inconvenience to be engineered away. It is the source of the deepest limit in computing.