A worry left over from the last guide
In the previous guide we pinned down the class P: the decision problems a Turing machine can solve in polynomial time, where the running time is at most some fixed power of the input length, like O(n^2) or O(n^3). It was a clean definition. But a careful reader should feel a splinter of doubt. The whole definition is hung on one very particular gadget — a single tape, one head, shuffling symbols back and forth one cell at a time. That is a deliberately impoverished machine. Why should the boundary of 'efficient' depend on such a quaint device?
Here is the worry made sharp. Suppose I solve a problem in O(n^2) steps on a machine with several tapes, so each subtask gets its own scratch space. If I now have to cram all that work onto a single tape — paying for the head to walk back and forth between regions that used to be separate tapes — my step count might balloon. Does it balloon enough to push the problem OUT of polynomial time? If yes, then P is an accident of the hardware: change the machine and the class changes, and 'P' means nothing absolute. If no, then P is a property of the PROBLEM, not the machine. This guide is about establishing, honestly, that the answer is no.
Many tapes onto one: a polynomial slowdown, not an explosion
Start with the cheapest upgrade: a multi-tape Turing machine, which is just an ordinary machine given k separate tapes, each with its own head, all moving in one step. The standard theorem says a single-tape machine can SIMULATE a k-tape machine, and the cost is gentle: if the multi-tape machine runs in t steps, the single-tape simulation runs in O(t^2) steps. Quadratic, not exponential. That square is the price of forcing many work areas to share one tape — but a square of a polynomial is still a polynomial, so the simulated machine stays inside P.
The mechanism is worth picturing, because the O(t^2) bound is not magic. Lay the k tapes side by side on one long tape, in interleaved tracks, and mark each head's current position with a special dot. To simulate one step of the multi-tape machine, the single-tape head makes one full sweep across all the marked regions to read what is under each virtual head, then a second sweep to update each one and move the dots. The catch: after t steps the used region can be about t cells wide, so each sweep costs O(t). With t steps to simulate and O(t) per step, the total is O(t^2). The slowdown is real, but it is bounded by a polynomial in the original time, which is exactly the guarantee we wanted.
Multi-tape machine, one step: Single-tape simulation of that step:
tape1: . . a [b] c . ...sweep RIGHT across all tracks...
tape2: . [x] y . . . read symbol under each * (the heads)
tape3: . . . [z] . . ...sweep LEFT, update + move each *...
^each [.] is a head cost per simulated step = O(t)
steps to simulate = t
one parallel step -----------> total single-tape cost = O(t^2)
Square of a polynomial is still a polynomial => stays in P.What about a real computer? The RAM model
A tape machine still looks nothing like the laptop on your desk, which can jump to any memory cell in one instruction — no shuffling a head across the whole tape. This is the random-access machine (RAM), the idealised model that real hardware and ordinary pseudocode actually match. Surely THIS is more powerful, and could solve in polynomial time things a Turing machine cannot? For raw computability, no: the RAM and the Turing machine decide exactly the same languages. For TIME, the answer is the one that matters here — a Turing machine can simulate a RAM (and vice versa) with only a polynomial slowdown, so the two models define the very same class P.
The simulation works in both directions, and seeing why keeps you honest about one subtle trap. A Turing machine imitating a RAM stores the RAM's memory as a list of (address, value) pairs on its tape; a single random access becomes a scan to find the right address, which costs a polynomial in the work done so far, not a constant. Going the other way, a RAM imitating a Turing machine just keeps the tape in an array and tracks the head index — cheap. The subtle trap: this all rests on the RAM using numbers of REASONABLE size. If you let a single memory cell hold an astronomically large integer and multiply two such giants in 'one step', you have smuggled in unrealistic power, and the polynomial equivalence breaks. Honest models charge for big numbers; with that fair accounting, P is preserved.
The thesis that makes 'P' a real word
Step back and read the pattern. Multi-tape onto single-tape: polynomial. RAM onto Turing machine: polynomial. The same holds for register machines, for two-dimensional tapes, for almost any sensible serial computer you can dream up — each simulates the others with at most a polynomial blow-up in time. Because polynomials are closed under composition (a polynomial of a polynomial is still a polynomial), chaining these simulations never escapes polynomial time. So the class you get is identical across all of them. That empirical-yet-sturdy observation has a name: the Cobham-Edmonds thesis, which proposes that 'solvable in polynomial time on a deterministic machine' is the right formal stand-in for 'efficiently solvable in principle', precisely because it does not depend on which reasonable machine you chose.
This is the deep reason P deserves a capital letter while a specific bound like 'O(n^3) on a 2-tape machine' does not. The exact exponent IS model-dependent — moving from multi-tape to single-tape can square it, turning an O(n^2) algorithm into O(n^4) — but the bare fact 'the exponent is some constant' is model-independent. Model-independence of P means we get to talk about a problem being in P without ever naming a machine, the way we talk about a number being prime without naming a numeral system. The membership is intrinsic to the problem.
Where robustness stops: the honest fine print
Model-independence is a powerful gift, but it is not unconditional, and pretending otherwise would be exactly the kind of comforting falsehood this course refuses. The thesis quietly says 'every REASONABLE model', and that word is load-bearing. There are two famous escape hatches where the polynomial-simulation guarantee is NOT known to hold, and they are the most interesting objects in the whole subject.
The first is nondeterminism. A nondeterministic machine — the jigsaw-puzzle model, allowed to guess and then verify — is NOT believed to be simulable by a deterministic one with only a polynomial slowdown. The best general simulation we know is exponential. Whether a polynomial one exists is exactly the P-versus-NP question, the central open problem of the field. So nondeterminism is deliberately left OUTSIDE the 'reasonable serial models' that all agree on P; it may or may not be a different beast, and nobody has proved which.
The second is quantum computation. A quantum computer is a genuinely different physical model, and the strong claim that EVERY physically realisable device simulates a Turing machine with only polynomial slowdown is the extended Church-Turing thesis — and quantum computing is the leading reason to doubt it. There are problems, factoring being the famous one, with a known polynomial-time quantum algorithm but no known polynomial-time classical one. Two honest cautions, though: this is about a SLOWDOWN that may exceed polynomial, not about computing anything previously uncomputable; and despite loose headlines, a quantum computer is NOT known to solve NP-complete problems efficiently. The robustness of P is real and load-bearing — but it is a claim about reasonable serial models, with these two famous frontiers honestly fenced off.