Turing Machines and Universality

In 1936, before any electronic computer existed, Alan Turing described the simplest machine that can compute anything computable: a tape, a head that reads and writes one symbol at a time, and a finite table of rules. Every computer since, from a phone to a rack of servers, computes exactly the same set of things as that machine. It computes them faster, never more of them.

That fact settles a question engineers argue about constantly. Every real programming language can compute the same things, so "can language X do this?" is almost never the real question. The real questions are what it costs to write, what it catches before running and how fast it runs, and those are the differences Chapter 13 was about.

The Machine

A Turing machine is a finite control, like the state machines of the first topic in this chapter, plus a tape it can move along, read and overwrite without limit. Each step does the same five things. It reads the symbol under the head, looks up the row for the current state and that symbol in its table, writes a symbol, moves one cell left or right or stays put, and changes state. There is nothing else: no arithmetic unit, no registers, no memory addresses.

The figure runs a machine that adds 1 to a binary number. It starts in a state called carry, with the head on the last digit of 1011, which is eleven. A 1 under the head becomes 0 and the head moves left, still carrying. The next 1 does the same. The 0 after that becomes 1 and the machine halts, leaving 1100, which is twelve. Four rules are the whole program. What this machine has that the stack machine of the previous topic lacked is memory it can revisit in any order: the head can go back to any cell, and that is the top of the ladder.

The Universal Machine

Turing's second idea matters more than the first. A Turing machine can read the description of another machine from its tape and carry out that machine's steps, one by one. One machine can run any machine. That is the stored-program idea: programs are data, the point of Chapter 2's first topic, and the processor of Chapter 3 fetches instructions from the same memory as the numbers they work on.

An interpreter is a universal machine in practice. CPython reads a program as bytes and makes itself behave like the machine that program describes, the loop of Chapter 13. A browser running JavaScript, a database running a stored procedure and a spreadsheet evaluating formulas are all doing the same thing.

Programdata on the tape

→

Universal machinean interpreter

→

Behaviourof that program

The Church–Turing Thesis

In the same year, Alonzo Church defined computation a completely different way, with the lambda calculus: nothing but functions applied to functions. Turing showed within a year that the two definitions compute exactly the same functions. Every model proposed since, from register machines to cellular automata to modern programming languages, has matched them.

The Church–Turing thesis says that anything a step-by-step procedure can compute, a Turing machine can compute. It is a thesis rather than a theorem, because "step-by-step procedure" is an intuition, not a definition, and an intuition cannot be proved equal to a formula. It can be tested, and in 90 years it has never been contradicted.

What Turing-Complete Takes

A system that can compute everything a Turing machine can is called Turing-complete, and it takes very little: a way to choose, a way to repeat without a fixed limit and memory that can grow without a fixed limit. Because the bar is so low, completeness turns up by accident. Conway's Game of Life, a grid of cells following two rules about their neighbours, is Turing-complete. So are C++ templates, which were meant to generate code at compile time, and SQL once recursive queries were added in the 1999 standard.

Strictly, no real computer is a Turing machine. A laptop has finite memory, so it is an enormous finite state machine with more states than there are atoms to count them. The model idealizes memory the same way Big-O idealizes n in Chapter 1: it describes what happens when you do not run out, and in practice that is the useful question.

Equal Power, Different Costs

Every general-purpose language computes the same functions. Python, Rust, SQL with recursion and a shell script differ in what is quick to write, in which errors are caught before the program runs, as Chapter 13 showed for types, and in how fast the result runs, which is a matter of the interpreter or compiler underneath.

So "Python cannot do X" is almost always a statement about a library, a runtime or speed. It is never a statement about computability. When a team says the language cannot do something, the useful follow-up is which of those three it means, because each one has a different fix.

The Price of Completeness

A Turing-complete language inherits every limit in the next topic: nobody can decide in general whether its programs finish, or what they do. Some languages give completeness up on purpose to keep those questions answerable. Regular expressions are one. Bazel's configuration language Starlark allows no recursion and no unbounded loops, so every configuration finishes. The Linux kernel's eBPF verifier accepts only programs it can show will finish, and has accepted loops since kernel 5.3 only when their bound is known.

The cost in systems you run is the configuration or template format that grew loops and conditions one feature at a time. Each addition was reasonable. Together they gave it the power of a program and took away the property that a tool could check it. That is the build configuration or CI pipeline that hangs instead of failing, and the template that no linter can say anything useful about.