線形加速定理
ここでは c = 1 / 2 の場合の証明の概略を述べる。いま M を時間量 f(n) で言語を決定するチューリング機械、k をテープ記号の個数、s を状態数とする。 M を模倣する新しいチューリング機械 M' を次のように構成する。M' のテープ記号の個数は k とし、各テープ記号は M の3つのテープ記号のチャンクを表すものと考える。M' のテープは M のテープを次のように圧縮して表現する。 M' の i 番目のセルは、M の 2i-1, 2i, 2i+1 番目のセルを表現する(これらブロックは重なりを持つことに注意)。
M のヘッドが現在のチャンクから隣のチャンクに移動するまでの M の状態遷移は、 M' の1ステップで模倣できる。というのも M のヘッドがひとつのチャンクに留まり続けている間に取りうる状態遷移は繰り返しを除けば高々 sk だからである。