加速定理
例として回文(palindrome)を認識する1-テープチューリング機械を考える。次のアルゴリズムは O ( n 2 ) {\displaystyle O(n^{2})} の時間計算量を持つ。
入力の左端の記号を読み取り空白記号を書き込む。このとき読み取った記号を記憶しておく。
入力の右端までヘッドを動かして、記号を読み取る。このとき左側にあった記号と異なるなら拒否して停止する。さもなくば空白記号を書き込む。
空白で埋まったら受理する。さもなくば(1)に戻る。(左端に戻るのは非効率であるから、左右を入れ替えて同じことを繰り返してもよいが、計算量のオーダーは変わらない。)
同じ問題を O ( n ) {\displaystyle O(n)} で解く次のような2-テープチューリング機械が考えられる。
入力を作業用テープにコピーする。