What is a computation?

Every level of this site computes something. Gates compute Boolean functions, the CPU computes the effect of an instruction, a program computes its output, an app computes what to show on screen. But what is a computation? What do all of these have in common, and is there anything a computer can't do, however fast and big it gets?

Those questions were answered in the 1930s, before any electronic computer existed, by mathematicians trying to pin down what "a procedure" means. Their answers are still the foundation: they tell us what every computer can do in principle, why one machine can imitate any other, and why some problems can never be solved by any program.

Algorithms

An algorithm is a finite list of precise instructions that turns an input into an output. The word comes from the name of the 9th-century Persian mathematician al-Khwarizmi, whose book spread step-by-step methods for arithmetic, but the oldest algorithm still in daily use is older: Euclid's algorithm for the greatest common divisor, written down around 300 BC.

To find the GCD of a and b: if b is 0, the answer is a. Otherwise, replace (a, b) by (b, a mod b) and start again.

For 1071 and 462:

1071 = 2 × 462 + 147
 462 = 3 × 147 +  21
 147 = 7 ×  21 +   0     → the GCD is 21

This short recipe has everything that makes an algorithm:

• each step is definite: there's no judgment involved, a clerk or a machine can follow it;
• each step is effective: it can actually be carried out, with pencil and paper, in finite time;
• it terminates: the second number gets strictly smaller at every step, so it must reach 0;
• it's finite, but works for inputs of any size.

A recipe with "stir until it looks right" is not an algorithm; "stir for three minutes" nearly is.

What counts as a step?

In 1928, David Hilbert asked whether there was a mechanical procedure that could decide, for any statement of mathematical logic, whether it's provable: the Entscheidungsproblem, the "decision problem". To answer "no", you need to say exactly what counts as a mechanical procedure; otherwise someone can always claim a cleverer one exists.

In 1936, two answers appeared within months of each other. Alonzo Church defined computation with the lambda calculus, a system in which everything is a function applied to other functions. Alan Turing, in his paper On Computable Numbers, took a more physical approach: he imagined a person computing with pencil and paper, and stripped the process down to its bare minimum.

The Turing machine

A Turing machine has:

• a tape, divided into cells, unbounded in both directions, each holding one symbol from a finite alphabet (here 0, 1 and the blank _);
• a head that reads and writes one cell at a time and can move one cell left or right;
• a state, one of a finite set;
• a table of rules: for each (state, symbol read) pair, what to write, which way to move, and which state to enter next.

That's all. There's no arithmetic, no memory addresses, no variables: only a finite table and a tape. Here's a machine that adds 1 to a binary number. It starts in state right on the leftmost digit:

It walks right to the end of the number, turns back, and propagates the carry: every 1 becomes 0 until a 0 (or a blank, past the leftmost digit) becomes 1. Started on 1011 (eleven), it takes eight steps; the head's position is in brackets:

0  right  [1]011
1  right  1[0]11
2  right  10[1]1
3  right  101[1]
4  right  1011[_]
5  carry  101[1]_
6  carry  10[1]0_
7  carry  1[0]00_
8  halt   1[1]00_      → 1100, twelve

Here is the machine itself. The tape is the row of cells, the triangle is the head, and the colored tag under it is the state. At each step, the highlighted row of the table is the only rule that matches the current state and the symbol under the head: the machine has no other choice to make.

Run it on 1011 and it goes through the same nine configurations as the trace above and halts on 1100. Try 111: the carry runs off the left end, the machine writes a 1 on the blank there, and 111 becomes 1000, again in eight steps. Type any binary number and the same six rules add 1 to it; only the number of steps changes, with the length of the number and the run of 1s at its end.

Notice what happens when you press Play: one machine, the computer in front of you, is running a program that is another machine. That's the idea at the heart of this chapter.

The Church–Turing thesis

Turing machines look hopelessly weak. Yet with enough states, they can add, multiply, compare, sort, run any algorithm anybody has ever written down. Church's lambda calculus turned out to compute exactly the same functions as Turing machines, and so did every other definition proposed since: recursive functions, register machines, cellular automata, every programming language with unbounded memory.

The Church–Turing thesis states that this is no coincidence: anything that can be computed by an effective step-by-step procedure can be computed by a Turing machine. It's a thesis, not a theorem, because "effective procedure" is an informal idea; it can't be proven, only supported. Ninety years of new models, all equivalent, support it strongly.

A system that can compute everything a Turing machine can is called Turing complete. C, Python, JavaScript and the x86 instruction set are, given unlimited memory. So, by accident, are some very odd things: Conway's Game of Life, C++ templates evaluated at compile time. It takes surprisingly little: some memory to read and write, and a way to choose what to do next based on what was read.

Universality: one machine to run them all

Turing's most important idea is in the same 1936 paper. A machine's rule table is just a finite list of symbols, so it can be written on a tape. Turing described a universal machine: one fixed Turing machine that reads the description of any other machine on its tape, followed by that machine's input, and simulates it step by step.

That's exactly what a stored-program computer is. The CPU is a fixed piece of hardware; the program in memory says what to compute. The same chip runs a spreadsheet, a game or a Turing machine simulator, or an interpreter for another machine entirely, like the JVM-bytecode interpreter in the bytecode chapter, which is itself a program run by a universal machine.

The whole idea of levels rests on this. Each level is a virtual machine (see levels of abstraction), implemented by interpreting or translating it on the level below, and hardware and software are logically equivalent: anything one does, the other can do. Universality is the reason. By 1970, most ISAs were interpreted by a microprogram, a small interpreter built into the processor. Today, as the microprogramming chapter shows, the common instructions of a high-performance CPU are decoded directly by hardware into internal micro-operations, with microcode kept for the complex and rare ones. The balance moved, but the equivalence is the same.

Turing is sometimes credited with COLOSSUS, and COLOSSUS with breaking Enigma; in fact COLOSSUS was designed by Tommy Flowers against the Lorenz cipher, and Turing's wartime machine was the Bombe, used against Enigma. The levels of abstraction chapter has the history. Turing's real contribution is the idea of the universal machine, which every computer since the stored-program machines of 1948–49 has embodied.

One caveat on universality: a real computer has finite memory, so strictly speaking it's a (gigantic) finite-state machine, not a Turing machine. In practice the distinction rarely matters: when a program runs out of memory, we add more, or the problem was too big for any machine.

What no program can do

Universality has a dark side. If programs can take programs as input, we can ask questions about programs, and some of those questions have no algorithm.

The most famous is the halting problem: given a program p and an input x, does p eventually stop when run on x, or does it run forever? Turing proved that no program can answer this correctly for all p and x. The proof is short. Suppose someone gives us a function that does:

int halts(program p, input x);   /* 1 if p(x) stops, 0 if it runs forever. Always answers. */

Then we can write this program:

void paradox(program p) {
    if (halts(p, p))     /* would p stop when given its own text? */
        for (;;) { }     /* then loop forever */
    else
        return;          /* otherwise stop */
}

Now run paradox on its own text. If halts(paradox, paradox) says it stops, paradox loops forever. If it says it loops forever, paradox stops. Either answer is wrong. So halts can't exist, not because it's hard to write, but because its existence is a contradiction. The same argument answered Hilbert: there's no mechanical procedure to decide all of mathematics.

This isn't just a curiosity. By Rice's theorem (1953), every non-trivial question about what a program does (does it ever print "hello", does it ever access this array out of bounds, is it a virus?) is undecidable in general. That's why compilers can't find all bugs, why antivirus software relies on signatures and heuristics, and why a static analyzer must sometimes say "maybe": each of them answers a restricted or approximate version of an impossible question.

Simple-looking questions can be very hard even when they're not impossible. The busy beaver problem asks how many steps the longest-running halting Turing machine with n states can take (on a blank tape, with two symbols). For 4 states the answer is 107 steps. For 5 states it's 47,176,870, a value proven only in 2024, by a collaborative project that checked every 5-state machine with computer-verified proofs. For 6 states, no one knows, and the known candidates run far longer than there are atoms in the universe.

Computable versus efficient

The Church–Turing thesis says what can be computed; it says nothing about how fast. A Turing machine and a modern CPU can compute the same functions, but not at the same speed: our Turing machine needed 8 steps to add 1 to a 4-digit number, and would need more for longer numbers, while the CPU adds two 64-bit numbers in a single add instruction. Representation matters: the same computation can cost one step or many, depending on the machine.

What stays stable across all reasonable machines is the growth rate. A problem that needs a number of steps polynomial in the input size (n, n log n, n³) on one reasonable machine needs a polynomial number on any other. That's why complexity theory can talk about problems independently of hardware, and why the complexity chapter counts steps rather than seconds.

This splits problems into three rough kinds:

Whether every problem whose answers can be checked quickly can also be solved quickly (P versus NP) is the most famous open question in computer science. Most researchers believe the answer is no, and a lot rests on hardness: public-key cryptography depends on problems, like factoring large numbers, for which no efficient algorithm is known.

Takeaways

• An algorithm is a finite list of definite, effective steps that terminates: Euclid's GCD is one, 2,300 years old.
• A Turing machine (a tape, a head, a state and a table of rules) is the simplest complete model of computation; the binary incrementer adds 1 to 1011 in 8 steps.
• The Church–Turing thesis: anything computable by an effective procedure is computable by a Turing machine. Every general-purpose programming language and CPU is Turing complete, given enough memory.
• A universal machine runs any other machine from its description: that's the stored-program computer, and the reason interpreters, emulators and levels of virtual machines work.
• The halting problem has no algorithm, and by Rice's theorem neither does any non-trivial question about a program's behavior: tools can only approximate.
• Computable isn't efficient: some problems have fast algorithms (P), some can only be checked quickly (NP), and some can't be solved at all.