A MULTI-TRACK TURING MACHINE HAS ONE TAPE DIVIDED INTO k PARALLEL TRACKS. THE HEAD READS ALL k TRACKS OF A CELL AT ONCE AND WRITES ALL k AT ONCE. ┌───┬───┬───┬───┬───┐ │ a │ b │ a │ b │ B │ ← track 1 ├───┼───┼───┼───┼───┤ │ X │ B │ B │ Y │ B │ ← track 2 ├───┼───┼───┼───┼───┤ │ 0 │ 1 │ 1 │ 0 │ B │ ← track 3 └───┴───┴───┴───┴───┘ ▲ ONE head, reading all three ── THE KEY POINT ─────────────────────────────────────────── THERE IS ONLY ONE HEAD, AND IT READS AND WRITES A WHOLE COLUMN. This is what distinguishes multi-TRACK from multi-TAPE, which is the next topic. A multi-tape machine has INDEPENDENT heads that can be at different positions; A MULTI-TRACK MACHINE'S TRACKS ARE ALWAYS ALIGNED, because there is one head serving all of them. CONFUSING THE TWO IS THE COMMONEST ERROR IN THIS PART OF THE SYLLABUS. ── THE EQUIVALENCE ───────────────────────────────────────── A k-TRACK TURING MACHINE IS EXACTLY EQUIVALENT TO A SINGLE-TRACK TURING MACHINE — with NO loss of power and NO loss of speed. THE PROOF IS ONE SENTENCE: TAKE THE TAPE ALPHABET TO BE TUPLES. Γ_single = Γ₁ × Γ₂ × … × Γ_k A single symbol of the new alphabet IS a whole column of the old machine. Reading it reads all tracks at once; writing it writes all tracks at once. SO MULTI-TRACK IS NOT A DIFFERENT MACHINE AT ALL — IT IS A DIFFERENT WAY OF DRAWING THE SAME MACHINE, with the tape alphabet factored into components. THE ALPHABET GROWS MULTIPLICATIVELY: 2 tracks over a 3-symbol alphabet → 3² = 9 symbols 3 tracks over a 3-symbol alphabet → 3³ = 27 symbols 2 tracks over a 5-symbol alphabet → 5² = 25 symbols A FINITE ALPHABET STAYS FINITE HOWEVER MANY TRACKS ARE USED, which is all the definition requires. THE SIZE IS IRRELEVANT TO COMPUTABILITY — only finiteness matters. AND CRUCIALLY: THERE IS **NO TIME PENALTY**. Each step of the k-track machine is one step of the single-track machine. This is unlike the multi-tape case, where the simulation costs a quadratic slowdown — the difference being that here nothing needs to be searched for, since the tracks are already aligned under one head. ── WHAT TRACKS ARE USED FOR ──────────────────────────────── 1. KEEPING THE INPUT INTACT. Track 1 holds the original input, untouched; track 2 holds the working marks. The machine can therefore re-read the input after modifying its workspace — impossible on a single track without destroying data. 2. MARKING WITHOUT CHANGING THE ALPHABET. Instead of introducing marked symbols X and Y into Γ, put a marker on a second track directly above the symbol. CLEANER, because the input alphabet is left alone. 3. CARRYING A COUNTER. One track holds the data, another holds a binary counter that the machine increments as it works. 4. BINARY ARITHMETIC. Adding two binary numbers: track 1 holds the first number, track 2 the second, track 3 the running carry and result. The head sweeps right to left performing the addition column by column, EXACTLY AS ONE DOES BY HAND — which is the natural way to program it and impossible to arrange on a single track. 5. IMPLEMENTING THE TWO-WAY INFINITE TAPE, below. ── THE TWO-WAY INFINITE TAPE SIMULATION ──────────────────── A standard and elegant use, and a likely exam question. PROBLEM: some definitions give the machine a tape infinite in BOTH directions; the standard definition gives one infinite only to the right. Show they are equivalent. SOLUTION — FOLD THE TAPE AT THE ORIGIN ONTO TWO TRACKS: two-way tape: … c₋₃ c₋₂ c₋₁ [c₀] c₁ c₂ c₃ … becomes track 1: c₀ c₁ c₂ c₃ … (right half) track 2: # c₋₁ c₋₂ c₋₃ … (left half, reversed) A special marker # in the first cell of track 2 identifies the fold point. THE MACHINE KEEPS AN EXTRA BIT OF STATE recording which track it is currently "on". WHEN IT IS ON TRACK 2, THE DIRECTIONS ARE REVERSED — moving left on the original tape means moving right along track 2. REACHING THE FOLD SWITCHES TRACKS. SO A ONE-WAY INFINITE TAPE WITH TWO TRACKS SIMULATES A TWO-WAY INFINITE TAPE EXACTLY, step for step. THE "INFINITE IN BOTH DIRECTIONS" VARIANT ADDS NOTHING.

── WHY THESE EQUIVALENCE RESULTS MATTER ──────────────────── Multi-track is the first of a series of variants, each shown equivalent to the basic model: MULTIPLE TRACKS no cost at all TWO-WAY INFINITE TAPE no cost (via two tracks) STAY-PUT option no cost (replace S by R then L) LARGER TAPE ALPHABET no cost MULTIPLE TAPES quadratic time cost NON-DETERMINISM exponential time cost MULTIPLE HEADS polynomial cost TWO-DIMENSIONAL TAPE polynomial cost NONE CHANGES WHAT CAN BE COMPUTED. THE ARGUMENT THIS BUILDS TOWARD IS THE CHURCH-TURING THESIS. Each result says "this apparently more powerful machine is really the same machine". After enough such results, the claim that the model captures computation in general becomes difficult to resist — not because it is proved, but because every attempt to exceed it has failed in the same way. ── THE PRACTICAL VALUE IN CONSTRUCTIONS ──────────────────── In an exam or a proof, MULTI-TRACK MACHINES ARE USED FREELY WITHOUT APOLOGY, exactly as one uses subroutines when writing a program. The equivalence proof licenses this: describe the machine in whichever form is clearest, and the reader knows a single-track machine exists. A WORKED ILLUSTRATION — COMPARING TWO BINARY NUMBERS: "Track 1 holds x, track 2 holds y, aligned at the right. Sweep left to right. At the first column where the bits differ, the number with 1 there is larger — record the answer in the state and halt." ON A SINGLE TRACK this would require repeatedly walking between the two numbers, marking positions to remember where one had got to — dozens of states and a quadratic number of steps. ON TWO TRACKS IT IS A SINGLE LEFT-TO-RIGHT SWEEP. THE COMPUTATION IS IDENTICAL IN POWER AND ENORMOUSLY SIMPLER TO DESCRIBE, which is the whole point of the variant. ── THE DISTINCTION RESTATED ──────────────────────────────── MULTI-TRACK MULTI-TAPE ───────────────────────────────────────────────────────── number of tapes ONE k number of heads ONE k, INDEPENDENT head positions all tracks share each head moves one position separately simulation cost NONE — relabel the QUADRATIC in time alphabet what it gives parallel DATA at parallel data at the SAME position DIFFERENT positions ───────────────────────────────────────────────────────── THE LAST ROW IS THE ESSENTIAL DIFFERENCE, and it explains the cost difference too. TRACKS ARE FREE BECAUSE NOTHING HAS TO BE SEARCHED FOR; TAPES COST TIME BECAUSE THE SINGLE SIMULATING HEAD MUST TRAVEL BETWEEN THE POSITIONS THE INDEPENDENT HEADS OCCUPY.