Editing Linear speedup theorem (section)

== Tape compression ==
{{Anchor|Tape compression theorem}}

The proof of the speedup theorem clearly hinges on the capability to compress storage by replacing the alphabet with a larger one. Specifically, it depends on the '''tape compression theorem''':<ref name=":1">{{Cite book |last1=Balcázar |first1=José Luis |title=Structural Complexity I |last2=Díaz |first2=Josep |last3=Gabarró |first3=Joaquim |publisher=Springer-Verlag |year=1988 |isbn=3-540-18622-0}}</ref>{{Pg|page=|location=Theorem 2.1, 2.2}}<blockquote>If a language <math>L</math> is accepted by a Turing machine within space <math>s(n)</math>, then for any <math>c > 0</math>, there exists some Turing machine that accepts it within space <math>c \cdot s(n)</math>. The same holds for non-deterministic Turing machines.</blockquote>For non-deterministic single-tape Turing machines of time complexity <math>T(n) \ge n^2</math>, linear speedup can be achieved without increasing the alphabet.<ref>{{cite journal |last1=Geffert |first1=Viliam |date=1993 |title=A speed-up theorem without tape compression |journal=Theoretical Computer Science |volume=118 |issue=1 |pages=49–65 |doi=10.1016/0304-3975(93)90362-W |doi-access=free}}</ref>