Single-tape TM on {0ⁿ1ⁿ} · O(n²) by pairing

The language {0ⁿ1ⁿ : n ≥ 0} demands equal counts of 0s followed by equal counts of 1s. On a single-tape Turing machine with one head, you cannot count both groups in parallel — you have one moving part. Sipser's canonical algorithm (Example 7.2) uses the only strategy available: pair off one 0 with one 1, mark them both, rewind, repeat.

The two-tape contrast: a 2-tape TM solves the same problem in O(n). Copy 0s to tape 2, then march tape 1 right through the 1s while tape 2 marches left through the copied 0s, both in sync. Quadratic-vs-linear is the price of having only one tape.

Trace the algorithm on "000111" (n = 3 pairs):

• Pair 1. Mark leftmost 0 → X. Walk right to leftmost unmarked 1, mark Y. Tape: X 0 0 Y 1 1. ≈ 6 steps.
• Pair 2. Rewind. Mark next 0 → X. Walk right, mark next 1 → Y. Tape: X X 0 Y Y 1. ≈ 12 steps.
• Pair 3. Rewind. Mark next 0 → X. Walk right, mark next 1 → Y. Tape: X X X Y Y Y. ≈ 18 steps.
• Verify. Rewind. Scan: no unmarked 0 → accept.

For n = 3, ≈ 18 steps. For n = 6, ≈ 72 steps. Doubling input quadruples work — the quadratic signature.

• The order matters. The algorithm must also reject inputs like "1100" or "010101" — anything where 0s and 1s are interleaved or out of order. A first-pass structural scan checks the 0*1* shape before pairing begins.
• Each pair's O(n) hides the rewind. The constant inside is ≈ 3: walk right to find 1, walk all the way back, then start the next pair. Including rewinds is what makes the lower bound Θ(n²), not just O(n²).
• Marking is non-destructive on the alphabet. X and Y are new symbols added to Γ (tape alphabet). They aren't 0 or 1 — they're "consumed 0" and "consumed 1." The TM's alphabet must include them.

• Q1. Why exactly Θ(n²)?
  n/2 pairs × O(n) per pair = O(n²). The matching lower bound comes from a crossing-sequence argument: every bit of "information transferred" between left and right halves requires the head to physically cross the middle. With n bits to communicate, you need Ω(n) crossings, each of cost Ω(n).
• Q2. Can a single-tape TM do better than Θ(n²)?
  No. The crossing-sequence lower bound is tight. Adding a second tape, two heads, or random-access — any of these gets you to O(n). The slowdown is the price of single-tape sequentiality.
• Q3. Why doesn't this break P?
  O(n²) is still polynomial. P is robust across reasonable machine models — single-tape, multi-tape, RAM, all polynomial-time equivalent. The constants and exponents may change, but the class P does not.
• Q4. Is there a faster single-tape algorithm using cleverer marking?
  Sipser §7.2 covers a variant that marks 0s in groups, achieving the same Θ(n²) but with better constants. The asymptotic class doesn't change.

Sipser: Example 7.2 (the pair-off algorithm), Theorem 7.8 (multi-tape simulation). Lecture notes: Module 4 slides 3–4. Companion problem: P19 (two-tape race).