線形加速定理
このようにして M の複数ステップを M' の1ステップで模倣できた。
各チャンクは重なりを持つので重なりあった部分で矛盾した記号が現れうる。この場合はヘッド位置に最も近いチャンクが正しい。ヘッドがあるチャンクから次のチャンクに移動したときは、もとのチャンクの重なりあった部分のシンボルをチューリング機械の状態で一時的に記憶しておき、記号の不整合が発生したら正しい記号をコピーしてやればよい。
この構成は M' の計算の1ステップが少なくとも M の計算の2ステップに対応することを要請する。したがって M' は入力を圧縮表現に変換する線形のステップ数を除けば f(n)/2 ステップで M の実行を模倣する。
この証明は容易に全ての c > 0 に一般化できる。それにはチャンクの大きさを十分に大きく取ればよい。同様の方法で時間量を空間量に置き換えたものが証明できる。これはテープ圧縮定理として知られる。