Abstract
Machine-checked Isabelle/HOL proof of the linear speedup theorem for multitape Turing machines, in deterministic and nondeterministic form, via the alphabet-enlargement construction. The theorem originates with Hartmanis and Stearns; the textbook proof followed here, together with its nondeterministic corollary, is due to Hopcroft and Ullman.
Given a machine \(M\) and block size \(m > 0\), the enlarged machine \(M' = \mathrm{alphabet\_enlarge}\, m\, M\), over alphabet \(\Sigma_M^m \cup \{\Box, \rhd\}\), simulates \(m\) steps of \(M\) per step, reading its input in blocks of \(m\) symbols; a wrapping step folds the block encoding back in so results compare languages over \(M\)'s original alphabet.
The session Multitape_Alphabet_Enlargement shows that \(M'\) accepts the encoded input iff \(M\) accepts \(w\), and that if \(M\) accepts \(w\) in time \(T(n)\) then \(M'\) does so in time \(2\lceil n/m\rceil + 8\lceil T(n)/m\rceil + 4\), with no determinism hypothesis. Wrapping this yields the Hopcroft–Ullman speedup corollaries for machines with at least two tapes, proved twice: for deterministic machines, where the result stays deterministic, and with no determinism hypothesis, giving \(\mathrm{NTIME}(cn) = \mathrm{NTIME}((1+\varepsilon)n)\) and \(\mathrm{NTIME}(T(n)) = \mathrm{NTIME}(c \cdot T(n))\), corollaries Hopcroft and Ullman state without proof. For a linear bound \(T(n) \le d_0 n + b\) and \(\varepsilon = 1/q\), a machine \(M''\) with \(L(M'') = L(M)\) runs in time \((1+\varepsilon)|w| + K\), \(K = 28 + 8d_0 + 8b\), matching Hopcroft–Ullman's \((1+\varepsilon)n\); for super-linear \(T\), \(M''\) runs in time \(\varepsilon\,T(|w|) + K\). The clean bound \((1+\varepsilon)|w|\), without \(K\), holds for \(M''\) once \(|w|\) passes the explicit threshold \(q(q+1)K\), and for all inputs once the encoder decides the shorter ones from a finite table while reading them, as in Hopcroft and Ullman's proof; that table exists but is not computed.
This session depends on Multitape_TM_Substrate and HOL-Library.
The Claude family of AI models, via Claude Code, was used for proof engineering.
License
Note
Generative AI was used for proof engineering and to write descriptions of the results, together with human design, steering, and review.
History
- November 10, 2026
- The block size is a number: alphabet_enlarge m M replaces alphabet_enlarge M,
whose blocks were indexed by a type 'c :: enum, and types lose the parameter
'c. A block is a function on {..
- October 28, 2026
- Added a convention form of Theorem 12.4 with no additive constant, deciding short inputs by a finite table as in Hopcroft and Ullman's proof (Wrap_Prefix_Patch, Wrap_Prefix_Runs), and a speedup theorem above a linear band (Wrap_Band_Speedup). Added Wrap_Speedup_Arithmetic, the arithmetic that turns the raw speedup bound into the (1+ε)n form. Time bounds now cover rejecting runs as well as accepting ones, and the encoding wrap rejects whenever the source does. Removed lemmas that duplicated the substrate's or others in this entry, and a vacuous hypothesis of the speedup theorems. Names follow the substrate's renaming. Updated abstract.
Topics
Session Multitape_Alphabet_Enlargement
- AlphabetEnlargement_Defs
- AlphabetEnlargement_Substeps
- AlphabetEnlargement_Delta
- AlphabetEnlargement_Simulation
- AlphabetEnlargement_Uniqueness
- AlphabetEnlargement_BufferArith
- AlphabetEnlargement_Window
- AlphabetEnlargement_Codec
- AlphabetEnlargement_ValidationStep
- AlphabetEnlargement_ValidationBound
- AlphabetEnlargement_ComputeCorrect
- AlphabetEnlargement_SS4
- AlphabetEnlargement_OutputWF
- AlphabetEnlargement_ForwardCells
- AlphabetEnlargement_ForwardStep
- AlphabetEnlargement_ForwardStage
- AlphabetEnlargement_Acceptance
- AlphabetEnlargement
- AlphabetEnlargement_Reverse
- Wrap_Base
- AlphabetEnlargement_Pack
- Wrap_Defs
- Wrap_Reset
- Wrap_Run
- Wrap_Encoder
- Wrap_Forcing
- Wrap_Prefix_Patch
- Wrap_Prefix_Runs
- Wrap_Canonical
- Wrap_Language
- Wrap_Time
- Wrap_Speedup
- Wrap_Speedup_Arithmetic
- Wrap_Convention
- Wrap_Band_Speedup