One-tape time in two-fifths-power space

Machines with one writable tape: blocks, visits, controllers and the local replay of a list of controllers. Finite fields of characteristic two, polynomial extensions of Boolean functions, and an evaluator that computes words defined by rules with three shared registers. The theorem: T steps of a machine with one writable tape are simulated in about T^(2/5) bits of storage, with a complete proof. Several writable tapes in about sqrt(T) bits; a lower bound for time from the space hierarchy theorem, which is a named hypothesis. The course is an exposition of OpenAI's proof (2026).

Five lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

  1. One-tape machines, blocks and visits
  2. Polynomials for Boolean functions
  3. An evaluator with one pool of registers
  4. Histories, checkpoints and the theorem
  5. Several writable tapes, and lower bounds for time

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites