A k-TAPE TURING MACHINE HAS k SEPARATE TAPES, EACH WITH ITS OWN INDEPENDENT HEAD. THE TRANSITION FUNCTION READS ALL k HEADS AT ONCE AND WRITES AND MOVES ALL k INDEPENDENTLY: δ : Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ So one step reads a k-tuple of symbols and produces a new state, a k-tuple of symbols to write, and a k-tuple of directions. THE INPUT starts on tape 1; the other tapes begin blank. ── THE ESSENTIAL DIFFERENCE FROM MULTI-TRACK ─────────────── THE HEADS MOVE INDEPENDENTLY. On a multi-track machine one head serves all tracks, so the tracks are permanently aligned. HERE HEAD 1 MAY BE AT CELL 5 WHILE HEAD 2 IS AT CELL 900. THAT INDEPENDENCE IS THE WHOLE OF THE ADVANTAGE — and, as the simulation shows, the whole of the cost. ── THE EQUIVALENCE THEOREM ───────────────────────────────── EVERY k-TAPE TURING MACHINE HAS AN EQUIVALENT SINGLE-TAPE TURING MACHINE. THE CONSTRUCTION uses the multi-track idea of the previous topic. Represent the k tapes on ONE tape with 2k TRACKS: · tracks 1, 3, 5, … hold the CONTENTS of tapes 1, 2, 3, … · tracks 2, 4, 6, … hold a single MARKER showing where each virtual head is ┌───┬───┬───┬───┬───┐ │ a │ b │ a │ B │ B │ tape 1 contents ├───┼───┼───┼───┼───┤ │ │ ▲ │ │ │ │ tape 1 head marker ├───┼───┼───┼───┼───┤ │ 0 │ 1 │ 1 │ 0 │ B │ tape 2 contents ├───┼───┼───┼───┼───┤ │ │ │ │ ▲ │ │ tape 2 head marker └───┴───┴───┴───┴───┘ TO SIMULATE ONE STEP OF THE k-TAPE MACHINE: 1. SWEEP LEFT TO RIGHT across the whole used region, recording in the finite control the symbol under each of the k markers. 2. Consult δ to decide what to write and how to move. 3. SWEEP BACK, updating each marked cell and shifting each marker one place. IF A HEAD RUNS PAST THE WRITTEN REGION, shift everything right to make room — an extra cost, but bounded. ── THE COST, AND WHY IT IS QUADRATIC ─────────────────────── A k-TAPE MACHINE RUNNING IN T(n) STEPS IS SIMULATED BY A SINGLE-TAPE MACHINE IN O(T(n)²) STEPS. THE ARGUMENT IS WORTH FOLLOWING BECAUSE IT EXPLAINS THE EXPONENT: · After T steps, no head can have moved more than T cells from the start, so THE USED REGION IS AT MOST O(T) CELLS WIDE. · Simulating ONE step requires a full sweep of that region to find all k markers, and a sweep back — COST O(T). · There are T steps to simulate. · TOTAL: T × O(T) = O(T²). ∎ NUMERICALLY: T = 10 → about 100 steps T = 1,000 → about 1,000,000 steps T = 1,000,000 → about 10¹² steps THE PENALTY IS SEVERE IN PRACTICE AND IRRELEVANT IN COMPUTABILITY — a polynomial slowdown cannot turn a halting computation into a non-halting one, so the CLASS of recognised languages is unchanged. ── THE CONCRETE GAIN: PALINDROMES ────────────────────────── The standard illustration of why extra tapes matter. ON ONE TAPE, recognising { w : w = wᴿ } requires comparing the first symbol with the last, the second with the second-last, and so on. EACH COMPARISON NEEDS A FULL TRAVERSAL of the tape, giving Θ(n²) time. ON TWO TAPES: "1. Copy the input to tape 2. 2. Move head 1 to the left end and head 2 to the right end. 3. Move head 1 RIGHT and head 2 LEFT in step, comparing the symbols at each position. 4. If they ever differ, REJECT; if the heads cross, ACCEPT." THE HEADS MOVE IN OPPOSITE DIRECTIONS SIMULTANEOUSLY, which a single head cannot do. THE TIME IS Θ(n). THE MEASURED DIFFERENCE: n = 10 : 1-tape ~ 100 vs 2-tape ~ 20 n = 100 : 1-tape ~ 10,000 vs 2-tape ~ 200 n = 1,000 : 1-tape ~ 1,000,000 vs 2-tape ~ 2,000 THE RATIO IS n/2 AND GROWS WITHOUT BOUND. A genuine asymptotic separation, not a constant factor. AND THE SEPARATION IS PROVABLE: IT IS KNOWN THAT PALINDROMES REQUIRE Ω(n²) TIME ON A SINGLE-TAPE TURING MACHINE, so the two-tape advantage is real rather than an artefact of a poor single-tape algorithm.

── OTHER USES OF EXTRA TAPES ─────────────────────────────── 1. A WORK TAPE separate from the input, so the input is never destroyed and can be re-read. 2. AN OUTPUT TAPE, written left to right and never re-read — the standard arrangement for a transducer. 3. A COUNTER TAPE holding a number in binary, incremented as the machine works. 4. A STACK, simulated on its own tape. 5. SORTING AND MERGING, where several sequences are traversed at once. THE PATTERN: EXTRA TAPES REPLACE HEAD TRAVEL WITH PARALLEL ACCESS. Anything requiring the machine to compare or combine data at distant positions becomes dramatically cheaper. ── THE STANDARD COMPLEXITY MODEL ─────────────────────────── Complexity theory conventionally uses a machine with: · a READ-ONLY input tape · one or more READ-WRITE work tapes · a WRITE-ONLY output tape THE READ-ONLY INPUT TAPE IS ESSENTIAL FOR SPACE COMPLEXITY: if the input counted as workspace, no computation could ever use less than n space, and the sublinear space classes such as L (logarithmic space) would be empty. THIS IS WHY THE MODEL IS SPECIFIED SO CAREFULLY IN THE LATER COMPLEXITY TOPICS — the definitions depend on it. ── THE INVARIANCE THESIS ─────────────────────────────────── A refinement of the Church-Turing thesis that governs complexity theory: ALL REASONABLE SEQUENTIAL MODELS OF COMPUTATION SIMULATE ONE ANOTHER WITH AT MOST POLYNOMIAL OVERHEAD. · k-tape TM → 1-tape TM: quadratic · RAM → TM: polynomial · TM → RAM: polynomial · every real computer → TM: polynomial THIS IS WHY THE CLASS **P** IS ROBUST. "Solvable in polynomial time" means the same thing on a Turing machine, a RAM, a laptop or a supercomputer, because polynomial overhead composed with a polynomial bound is still polynomial. IT IS ALSO WHY COMPLEXITY THEORISTS ARE RELAXED ABOUT THE EXACT MACHINE MODEL WHEN DISCUSSING P AND NP, AND VERY PRECISE ABOUT IT WHEN DISCUSSING LINEAR OR SUBLINEAR BOUNDS — where a quadratic simulation cost would swamp the result being stated. THE ONE MODEL THAT MAY BREAK THE THESIS IS THE QUANTUM COMPUTER, which is believed — though not proved — to solve some problems with more than polynomial speedup over classical machines. IT DOES NOT CHANGE WHAT IS COMPUTABLE, only how fast; a quantum computer computes exactly the same functions as a Turing machine. ── THE VARIANTS SUMMARISED ───────────────────────────────── VARIANT POWER TIME COST OF SIMULATION ─────────────────────────────────────────────────────────── multiple TRACKS same NONE two-way infinite tape same none stay-put option same none larger alphabet same constant factor MULTIPLE TAPES same QUADRATIC multiple heads same polynomial two-dimensional tape same polynomial NON-DETERMINISM same EXPONENTIAL (believed necessary) ─────────────────────────────────────────────────────────── EVERY ROW SAYS "SAME POWER". The column that varies is TIME, and that separation between COMPUTABILITY and COMPLEXITY is the boundary between the first half of this section and the second.