A second resource on the same notebook
On the last rung you learned to measure a Turing machine by time — counting the elementary moves of the head as a function of the input length n, taking the worst case, and smoothing away constants with big-O. Time is one of two natural resources a computation spends. The other is memory: how many cells of the tape the machine scribbles on before it halts. A machine can be fast yet greedy with paper, or slow yet thrifty. So we now ask the parallel question — not *how long does it take?* but *how much room does it need?* — and the answer is space complexity.
The setup is reassuringly familiar. Just as time complexity was a function T(n), space complexity is a function S(n): the maximum number of tape cells the machine ever has marked at once, over all inputs of length n, in the worst case. We measure it against the same n — the length of the input string — and we apply the same big-O lens, ignoring constants and low-order terms so the answer describes the problem and not the bookkeeping of one particular machine. Everything you internalised about honest measurement carries straight over; only the quantity we tally has changed from moves of the head to cells of the tape.
The trick that makes sublinear space possible
There is an immediate problem. A plain Turing machine reads its input on the tape, so those n cells are already occupied before the machine writes a single thing of its own. By that count, no machine could ever use less than n space — it has to hold the input somewhere. That would make the whole question dull: space would always be at least linear, and the most interesting territory, the tiny-memory machines, would be invisible. So the field adopts a small, decisive convention to charge memory honestly.
The fix is the work-tape convention: give the machine two tapes with different rules. One is a read-only input tape holding the n input symbols — the head may slide along it and look, but never write — and crucially its cells do not count toward space. The other is one or more read-write work tapes (scratch paper), and only the cells used there are charged as space. Think of an exam where you are handed a printed question sheet you may read as often as you like but cannot mark on, plus a thin pad of scratch paper; your "space" is how much of the pad you fill, not the question sheet you were given for free.
Why space is so different from time
Space has one property time does not: it is reusable. Each step of a computation is gone forever once spent, but a work-tape cell can be erased and written over again and again. This is the deep reason space turns out to be a more forgiving resource than time. A machine can take an astronomical number of steps while never using more than a modest patch of tape, simply by overwriting that patch repeatedly. So for the same task, the space bound is often dramatically smaller than the time bound — and the two need not move together at all.
But the relationship is not free in the other direction. If a machine runs for t steps, it can mark at most t new cells (one per step at most), so space is at most time: S(n) is at most T(n). The reverse, far more surprising, also holds and bounds time by space. A machine using S(n) work cells has only finitely many distinct total snapshots — its state, its head positions, and the contents of those S(n) cells. If it ever repeats a snapshot it would loop forever, so a machine that halts can run for at most as many steps as it has distinct snapshots, which works out to roughly 2^(O(S(n))) — exponential in the space. In short, a little space can hide an enormous amount of time.
Two resources on one Turing machine
read-only INPUT tape (n cells, FREE -- never counted)
+---+---+---+---+---+---+
| 1 | 0 | 1 | 1 | 0 | 1 | <-- head may read, never write
+---+---+---+---+---+---+
read-write WORK tape (CHARGED -- this IS the space)
+---+---+---+
| x | 0 | _ | ... <-- erase & overwrite freely; reusable
+---+---+---+
<-- S(n) = high-water mark of cells used here -->
log-space S(n) = O(log n) : a few pointers into the input
poly-space S(n) = n^k : PSPACE
Relations: S(n) <= T(n) (each step marks <= 1 new cell)
T(n) <= 2^(O(S(n))) (only that many distinct snapshots)Naming the regions: a new class map
Just as bounding time gave us P and NP, bounding space carves out a fresh family of space-complexity classes, each collecting the languages a machine can decide within some budget of work cells. The headline tiers, from thrifty to lavish: L, the problems solvable in O(log n) space on a deterministic machine; NL, the same budget but allowing a nondeterministic machine; and PSPACE, the problems solvable in polynomial space — n, n^2, or any n raised to a fixed power. These mirror the time classes you already know, but with the cell count as the meter instead of the step count.
The time-vs-space relations above let us stitch these into one grand chain that runs across both rungs: L is in NL is in P is in NP is in PSPACE is in EXPTIME. Each inclusion has an honest one-line reason. L is in NL because deterministic is a special case of nondeterministic. NL is in P because a log-space machine has only polynomially many snapshots, so you can search them in polynomial time. P and NP sit inside PSPACE because a polynomial-time machine marks only polynomially many cells. And PSPACE is in EXPTIME because, by the snapshot argument, polynomial space can be simulated in exponential time. This is the class map that the whole rung is built to chart.
What this rung will show you
With space defined and the map sketched, the rest of the rung explores it. The biggest payoff is that space, being reusable, behaves more tamely than time — and this produces results that look impossible at first. Two collapses stand out. Savitch's theorem shows nondeterminism is nearly worthless for space: any nondeterministic machine using S(n) space can be made deterministic using only S(n)^2 space, which forces PSPACE = NPSPACE — the space analogue of the P-vs-NP question simply vanishes. And the Immerman-Szelepcsenyi theorem shows NL is closed under complement, so NL = co-NL — for nondeterministic log space, a yes-instance and a no-instance are equally easy to certify, something flatly unknown (and widely doubted) for NP versus co-NP.
The rung then turns to where things get genuinely hard. PSPACE has its own notion of "hardest problems" — PSPACE-complete ones — and their natural form is not the puzzle-you-can-check of NP but a two-player game: a quantified boolean formula asking "does there exist a move for me such that for all replies of yours there exists a move for me ...", where the alternating exists/for-all quantifiers are exactly the back-and-forth of optimal play. Finally, guide 5 reveals how we prove any of these classes are different at all: a diagonalization argument — the same self-referential trick that made the halting problem undecidable — used in the hierarchy theorems to show that strictly more space (or time) buys strictly more power.
Hold one honest caveat as you climb. The inclusions are theorems but the separations are mostly conjectures: we believe L, NL, P, NP, and PSPACE are all genuinely different, yet we have proved almost none of these gaps. The little we can prove is exactly the hierarchy-theorem endpoints. Keeping straight which facts are settled and which are merely suspected is the discipline that makes this rung honest — and it is why questions like P vs NP remain among the great open problems of the subject rather than dusty closed cases.