What Is Computation?
The Core Idea
At its heart, computation is deceptively simple: it is the process of transforming information according to a finite set of unambiguous rules. Take some input — a list of numbers, a string of letters, an image encoded as bits — apply a precise sequence of steps, and produce an output. Nothing mystical happens along the way. Every act of computation, from adding two integers to rendering a photorealistic frame in a video game, reduces to operations on symbols carried out mechanically, without insight or judgment.
This definition matters because it separates computation from the machines that perform it. A computer is not required for something to be computed. A person with paper and pencil can compute. So can a system of gears, a relay network, or strands of DNA. The essence of computation lives in the procedure, not in silicon.
Turing Machines: A Model of Everything Computable
In 1936, the British mathematician Alan Turing asked what it means, precisely, to compute. His answer was a thought experiment of radical minimalism, now called a Turing machine. Imagine an infinitely long tape divided into cells, each holding one symbol from a small alphabet. A read/write head sits over one cell. The machine has a finite set of internal states and a fixed table of instructions. At each step, it reads the symbol under its head, consults the table, writes a new symbol, moves left or right, and transitions to a new state. That's all.
What makes this model astonishing is its power. Turing proved that any calculation that can be described as a definite, step-by-step procedure — anything we would recognize as an algorithm — can be performed by some Turing machine. This claim is known as the Church–Turing thesis. It implies that a machine this primitive is equivalent, in computational reach, to every laptop, server, and supercomputer ever built. Faster hardware computes faster; it does not compute more. The set of problems solvable by any physical computer is, in principle, the same set solvable by Turing's tape.
A related result follows from the idea of a universal Turing machine: one machine whose tape contains both data and a description of another machine. It can simulate that machine exactly. Universal machines are the theoretical foundation of the programmable computer — a single device that becomes whatever software describes.
What Computability Means
Turing did not stop at showing what machines can do; he showed what they cannot. Some perfectly well-defined problems admit no algorithmic solution at all. The most famous is the halting problem: given a program and an input, determine whether the program will eventually finish running or loop forever. Turing proved that no algorithm solves this for all possible programs. Any attempted solver can be defeated by feeding it a program designed to do the opposite of whatever the solver predicts — a contradiction proving impossibility.
This establishes the boundary of computability. Problems fall into three broad categories: those with algorithms that always work (decidable problems), those where an algorithm can confirm "yes" answers but may run forever on "no" answers (semi-decidable), and those with no algorithm whatsoever (undecidable). These limits are mathematical facts about logic itself, not engineering shortcomings. No future technology will solve the halting problem in full generality, because the proof rules out the very existence of such a procedure.
Computability also gives meaning to the word algorithm: an algorithm exists only if there is a finite, effective procedure — one a Turing machine could execute — that produces the correct answer for every valid input in a finite number of steps.
Algorithms versus Programs
The distinction between an algorithm and a program is like the distinction between a recipe and a particular meal cooked from it. An algorithm is an abstract specification: Euclid's method for computing greatest common divisors is a single idea, independent of language or era. A program is a concrete realization of that idea written in Python, Rust, or assembly, tuned to specific hardware, embedded among libraries and interfaces.
Several consequences follow. First, many different programs can implement the same algorithm; they may differ wildly in speed, size, readability, and correctness while computing identical results. Second, programs can contain bugs while their underlying algorithms are sound — implementation errors are distinct from design errors. Third, analyzing an algorithm abstractly lets us reason about its behavior on every possible input, something far harder to guarantee for a million-line codebase.
Programs inherit their guarantees from algorithms. When we prove an algorithm correct and then verify that our code faithfully implements it, we gain genuine confidence that software will behave as intended. Conversely, when software fails, the fault may lie at either level — a flawed idea or a flawed expression of a good one.
Computation, then, is best understood as a layered story: mathematics defines what is computable, algorithms specify how to compute it, and programs embody those specifications in running machines.