Why the machine model needs a proof
A verifier is convenient to describe using one tape for its input, another for a guessed certificate and a third for scratch work. A computation-table construction may instead expect one tape and one head. Moving between these descriptions is a mathematical step: the simulator must preserve the answer and keep its overhead within the resource bound being claimed.
This note supplies that step for a fixed finite number of ordinary Turing-machine tapes. We build the simulation, prove its invariant and count the actual sweeps. The construction is deliberately elementary. It proves polynomial-time robustness, but does not prove the sharper universal-simulation estimate used in the deterministic time-hierarchy note.
The two models
Definition 4.2.1
(Multitape Turing machine)
Fix a positive integer and a finite tape alphabet containing the input symbols and a blank symbol. A -tape machine has one finite control and two-sided tapes, each indexed by integers. In one transition it reads the scanned symbols, changes state, writes one symbol on each tape and moves each head by an element of . The number , alphabet and transition table belong to the fixed machine; they are not part of its input.
On input , tape one contains at coordinates and is blank elsewhere. The remaining tapes are blank. All heads start at coordinate zero, including when . Acceptance and rejection are designated halting states. We count transitions, and a time bound bounds the steps on every input of length .
The simulator has one two-sided tape, one head and a fixed finite alphabet that may be larger than . A larger alphabet is allowed in this model: its size is a constant determined by the simulated machine. We are proving a result about time, with the input stored on the counted tape. This is not a simulation preserving logarithmic work space with a separate uncounted input tape.
Put the virtual tapes into tracks
Definition 4.2.2
(Track representation of virtual tapes)
At each represented coordinate , one physical cell stores a record containing the virtual tape symbols and two head-marker bits for each track. Call the marker sets old and new. A delimiter at either end bounds the represented interval. The simulated control state is held in the simulator's finite control.
At the beginning of a simulated transition, the invariant is:
- Each virtual tape has exactly one old marker, at its current head position; every new marker is clear.
- The records contain exactly the current virtual tape symbols in the interval; all virtual cells outside it are blank.
- Every virtual head is inside the interval, and the finite control stores the correct simulated state.
There are only finitely many possible records: for example, choices suffice before adding delimiters. Thus a record can be one symbol of a fixed alphabet. Storing symbols at once is legitimate because is fixed; it is not a unit-cost operation on an input-dependent number of tapes.
Initialization scans the input once, replaces each input symbol with its record and supplies blank symbols on the other tracks. For empty input, it creates a blank record at coordinate zero. It marks coordinate zero on all tracks, adds one blank record at each end and places delimiters beyond those records. This takes time. If , we can use the initial interval , containing records.
Worked example 4.2.3
(Two heads at one physical position)
Suppose , tape one contains and tape two is blank. At coordinate zero the record contains symbols and both old markers. These are two virtual heads, represented by two different bits in one record. The single physical head reads the whole record in one transition. Later the virtual heads may separate, while the physical head visits their records at different times.
One virtual transition in a constant number of sweeps
First extend the interval by one blank record at each end, moving each delimiter one position outwards. The old endpoint records remain unchanged. A constant number of traversals suffices; locating the far delimiter is charged to the sweep cost. This extension ensures that every head destination for the coming transition is represented, even if an old head was at an endpoint.
Next sweep from left to right. On track , the unique old marker identifies its scanned symbol . Store the tuple in finite control. Together with the simulated state, it determines the transition: the next state, symbols to write and directions to move. These data have constant size for our fixed machine.
Sweep back across the interval and perform the update. Whenever a record has an old marker for track , write the prescribed symbol on that track and clear that old marker. Make a new marker for track at the destination: the same record or its immediate neighbor, according to the prescribed direction. To reach a neighboring record, the physical head can make a constant-length excursion and return before continuing its sweep. It preserves every other field of any record it visits. If several tracks have old markers in one record, process their updates in a fixed track order.
The update sweep processes only old markers. A destination may already have been visited, or may lie ahead; neither case changes which old markers it processes. A neighboring excursion does not invoke the update routine recursively. The machine remembers in finite control that it is completing one local excursion and then resumes the main sweep. There are old markers altogether, so there are at most such excursions.
Finally sweep across the interval to replace every new marker by an old marker. Update the simulated state and return to the chosen boundary for the next cycle. The represented interval after cycles may be , with records. Its size grows by two per cycle, regardless of how the virtual heads move.
Theorem 4.2.4
(The simulation invariant is preserved)
After each complete cycle, the records and stored state encode exactly the configuration obtained by one transition of the original machine. In particular, the simulator accepts or rejects exactly when the original computation does.
Proof
(Induction on the number of cycles)
The initialized representation satisfies the invariant. Suppose it holds before a cycle. Enlarging the interval adds only blank cells, matching the virtual cells outside the old interval. The collection sweep reads exactly the old scanned symbols, so it selects exactly the original transition. For each track, the update changes only the scanned symbol and places exactly one new marker at the prescribed destination. All other symbols on that track are unchanged. New markers cannot trigger another update, so no virtual transition is applied twice. Cleanup makes the new positions the next cycle's unique old markers and clears the new fields. The stored next state is also correct. This proves the claim by induction on the number of cycles. A simulated halting state ends the simulation; an initially halting machine can be recognized after initialization.
Proof X-ray
Where the old and new markers carry the induction
Besides the update rule, the induction spends three facts. The collection sweep ends before any write, so the transition is selected from the old configuration alone; this is what “selects exactly the original transition” means. Writes create only new markers and the update sweep reacts only to old ones, so nothing is applied twice, wherever the destination lies relative to the sweep. Cleanup then restores the invariant by renaming roles, not by moving data. The two buffer records added at the ends are what make clause 3 of the invariant survive a head step outward, and a fixed is what lets the tuple of scanned symbols sit in finite control. Remove the old/new distinction and the failure in the example below appears.
The next example shows what the separation of the two marker fields rules out.
Counterexample mode
Why one undifferentiated head marker is dangerous
Consider an update sweep moving left to right and a virtual rule that moves a head right. If the routine clears the mark at coordinate zero and immediately places an ordinary head mark at coordinate one, it may reach coordinate one next and apply the rule again. One virtual transition has then moved the head twice, possibly repeatedly until a boundary. Reversing the sweep does not solve the general problem, because machines can also move left. Separate old and new fields solve both directions with one invariant.
Count physical steps, not virtual instructions
Theorem 4.2.5
(A quadratic-overhead simulation)
For every fixed deterministic -tape machine with running time at most , the construction gives a deterministic single-tape machine with running time
If , this is . The hidden constant may depend on the fixed simulated machine, including and its alphabet.
Proof
(Summing the cost of all cycles)
At cycle , before which transitions have been simulated, the represented interval has records, including its newly added buffers. There are a fixed number of sweeps, at most constant-length excursions and constant work per visited record. The cycle therefore costs . If the original machine takes steps, initialization and all cycles cost at most
which gives the displayed bound. For the sum is empty and initialization still costs . The simulator does not need to know or compute a clock: it repeats cycles until the simulated machine halts. The bound analyzes that behavior from outside.
Worked example 4.2.6
(A polynomial bound stays polynomial)
Suppose a fixed three-tape verifier takes at most transitions on an encoded instance-certificate pair of total length . The simulator takes transitions. A subsequent single-tape computation-table construction can use this larger polynomial bound. It must use the simulator's bound, not retain the original cubic deadline unchanged.
Worked example 4.2.7
(A fast halt still pays for this initialization)
A machine that immediately rejects every input has . Our simulator scans and encodes the input before reporting rejection, taking time. The general bound permits this. The shortcut would give a meaningless zero bound here because its hypothesis fails. A specially optimized simulator could avoid that scan; the stated construction does not.
Nondeterminism and polynomial classes
For a nondeterministic machine, require the time bound on every branch. After collecting the scanned symbols, the simulator nondeterministically chooses one of the original machine's available transitions. All scanning, bookkeeping and cleanup steps are deterministic. A dead end without an available transition rejects unless it is already an accepting halt. The same invariant applies separately to each choice sequence. Thus there is an accepting simulator branch exactly when there is an accepting original branch, and every branch obeys the same overhead bound. No branching over possible tape contents or head positions is needed.
Corollary 4.2.8
(Fixed tape counts define the same P and NP)
The languages decidable in deterministic polynomial time are unchanged when one allows any fixed finite number of tapes instead of one. The same statement holds for nondeterministic polynomial time with an all-branches polynomial clock.
Proof
(Reducing to one tape)
A one-tape machine is already a -tape machine that ignores the other tapes. In the reverse direction, any polynomial bound can be enlarged to a polynomial without changing its classification; the simulation replaces it by another polynomial. The branchwise argument gives the nondeterministic version. Similarly, a deterministic multitape verifier with polynomial-length encoded certificates becomes a single-tape polynomial-time verifier without changing which certificates it accepts. The polynomial is measured in the actual encoded input length.
Common mistakes
Common mistake
(Polynomial robustness is not exponent preservation)
This result preserves polynomial membership, not exact time exponents. It does not prove that linear-time or quadratic-time classes agree across these models. It does not give the universal simulation assumed by the sharper time-hierarchy argument, nor any logarithmic-space preservation.
Common mistake
(The number of tapes must stay fixed)
Allowing to grow with input length would invalidate the constant-record argument and requires a different, explicitly costed model.
Exercises
Quick check
(For and , how many symbol-and-marker records are available before adding delimiters? Why is this finite number harmless?)
Solution · Answer
The symbol tuple has choices and the four marker bits have choices, giving records. This depends only on the fixed machine. A fixed finite alphabet can contain all these symbols; it does not grow with input length.
Quick check
(After seven simulated steps on an input of length four, what interval and record count can the stated expanding representation use?)
Solution · Answer
Here and , so the interval is and contains records, agreeing with .
Quick check
(A head moves left into a record already passed by the main update sweep. Why is its next position still represented correctly?)
Solution · Answer
The local excursion sets a new marker there and returns. The main update sweep need not revisit it: a later cleanup sweep crosses the whole interval and converts every new marker to an old marker. Its symbol changes only if that cell was the old scanned cell for the same track.
Quick check
(Why must scanned symbols be collected before any virtual write occurs?)
Solution · Answer
One original transition reads the entire old tuple simultaneously. Choosing its transition from partly updated information could change that tuple and select a different rule. Collection separates reading the old configuration from writing the next one.
Quick check
(An algorithm takes steps on a fixed multitape machine. What upper bound follows from this construction? Does that prove a matching lower bound?)
Solution · Answer
Enlarge the bound to at least and square it, obtaining for , with a finite convention for . This is an upper bound for one simulator. It proves neither that the original language needs this time nor that the simulation is optimal.
Quick check
(Why does bounding only accepting branches fail to supply the nondeterministic running-time claim made here?)
Solution · Answer
A rejecting branch might run arbitrarily long or forever. The construction follows that branch, so its time would not be polynomially bounded on all branches. The standard nondeterministic polynomial-time model imposes the clock on every branch; acceptance is the separate existential condition.
Quick check
(A verifier reads an encoded pair of length , where is polynomial, and runs in time. Show that its single-tape simulation remains polynomial in .)
Solution · Answer
The input length is polynomial in . Enlarge the verifier's time polynomial to dominate ; the simulation takes , hence polynomial time in . The accepted certificate set is unchanged by the invariant.
Quick check
(Can this proof replace a logarithmic-overhead universal-simulation lemma in a sharp time-hierarchy theorem? Explain precisely what is missing.)
Solution · Answer
No. We proved a bound quadratic in the simulated time when it dominates input length, for each fixed machine. A sharp hierarchy argument may need a universal simulator with only logarithmic time overhead and a controlled treatment of machine descriptions. Neither stronger overhead nor that universal construction is supplied here.