Computation
What machines can and cannot do
Description
In 1967, a mathematician and one of the founders of artificial intelligence, Marvin Minsky, published a textbook with a deceptively plain title: Computation. Its subtitle promised more — finite and infinite machines — and that pairing is the whole tension of the book. Minsky was already known around MIT for building strange devices and stranger arguments about thinking machines. Here he did something quieter and more ambitious. He wrote a rigorous, patient account of what a computing machine actually is, starting not from silicon or code but from the barest possible idea of a device that reads a symbol, changes its internal state, and moves on.
The book was written for students who had never seen this material, and it assumes almost nothing. It builds from the simplest machine imaginable — one with a handful of states and no memory to speak of — and climbs, step by careful step, toward machines powerful enough to compute anything computable at all. Along the way it draws a hard line. Some tasks lie inside the fence; others lie provably, permanently outside it, no matter how fast or how large the machine. That line is not an engineering limit waiting to be beaten. It is a mathematical fact.
What makes the book more than a manual is who wrote it and why. Minsky did not care about machines for their own sake. He cared about minds. If the brain is a machine, then the theory of machines is, in some quiet way, a theory of us — and its limits might be our limits too. That is the wager underneath the diagrams.
The question we’re asking : What exactly can a computing machine do, where does its power run out, and why did a founder of artificial intelligence think this mattered for understanding minds?What we’ll see : How the simplest machines are built up into the most powerful ones, and what that climb reveals about the fence around computation itself.
Table of contents
01Chapter 1 — The machine you can draw on a napkin
Minsky starts where almost nobody expects a book about computers to start: with something too simple to seem interesting. Imagine a device with a small set of internal states, reading symbols one at a time. It sees a symbol, and depending on which state it is currently in, it switches to another state and reads the next symbol. That is the whole apparatus. No screen, no memory bank, no stored program in the modern sense. This is the finite-state machine, and it is small enough to draw as a handful of circles and arrows on the back of an envelope.
The point of starting this small is to make the reasoning airtight. Because a finite-state machine has only finitely many states, we can say exactly what it can recognize. Feed it a string of symbols and it either ends in an accepting state or it doesn't. A turnstile, a traffic light, the logic that decides whether a sequence of coins adds up to the price of a soda — these are finite-state machines. Minsky treats them not as toys but as the atoms of the whole theory, the thing everything else is measured against.
02Chapter 2 — When a finite memory hits its wall
The task that breaks the finite-state machine is embarrassingly easy to state. Suppose we want a machine that reads a string of open and closed brackets and decides whether they are balanced — every open eventually matched by a close, properly nested. A person does this by keeping a running tally. Each open bracket adds one to the count; each close subtracts one; the string is balanced if the count never goes negative and ends at zero. Simple. And impossible for any finite-state machine.
The reason cuts to the heart of Minsky's argument. To check balance, you must be able to count arbitrarily high, because the string might contain a thousand nested brackets, or a million. But a finite-state machine has a fixed number of states, and a fixed number of states can only distinguish finitely many counts. Give it a string with more nesting than it has states to track, and it must, by simple counting, confuse two different situations and get one of them wrong. This is not a clever failure to patch. It is a wall built into the definition.
03Chapter 3 — The universal machine and the line it can't cross
The top of the ladder has a name and a face: the Turing machine, named for Alan Turing, who described it in the 1930s. Minsky presents it as the finite-state machine given the one thing it lacked — an unlimited tape it can read, write, and move across in both directions. That single addition changes everything. The tape is memory without a fixed ceiling, and with it the machine can, in principle, carry out any computation that can be carried out at all. This is not a claim Minsky makes lightly; it is the substance of what is called the Church-Turing thesis, the working assumption that this bare model captures the whole idea of 'computable.'
The truly startling result is universality. Minsky walks through the construction of a single Turing machine that can imitate any other, if you first write that other machine's description onto its tape. One fixed device, reading a description of a second device plus its input, produces exactly what the second would have produced. This is the abstract ancestor of every general-purpose computer: a machine is not built for one task but reads a program and becomes whatever the program says. The stored-program computer on the desk is a physical echo of this idea.
04Chapter 4 — Why a theory of machines is a theory of minds
Step back from the diagrams and it becomes clear why a founder of artificial intelligence spent a whole book on brackets and tapes. Minsky was never really asking what computers can do. He was asking what thinking is, and whether it belongs to the same family of processes he had just defined so precisely. If a mind is, at bottom, a machine that reads inputs, changes state, and acts — if the brain runs on the same logic as the tape and the stack — then the theory of computation is not a corner of engineering. It is the beginning of a theory of us.
The finite-and-infinite pairing in the title carries this weight. A brain is a physical object with finitely many parts, which makes it sound like a finite-state machine, penned in by the same walls. Yet human thought seems to reach toward the unbounded — counting without ceiling, imagining without end. Minsky's ladder gives this puzzle a shape rather than a slogan. The interesting question is not whether we are machines but which kind of machine, sitting on which rung, borrowing what sort of external memory to punch above our built-in limits. The paper we write counts on, the notes we keep, the stack we offload onto the world.
05Conclusion
The book that opened with circles and arrows on the back of an envelope closes on one of the sharpest results in mathematics. Minsky's climb — from a machine with a handful of states, through the stack, to the universal Turing machine and the wall of the halting problem — is a single argument stretched across every chapter: computational power is precise, it can be located in memory, and it comes with an edge that no amount of ingenuity will move. What machines can do is vastly more than intuition suggests. What they cannot do is not a temporary embarrassment but a theorem.