線形加速定理

計算複雑性理論におけるチューリングマシンの線形高速化定理は、任意の実数c  > 0 と、問題をf ( n ) の時間で解く任意のkテープチューリングマシンが与えられた場合、同じ問題を最大でf ( n )/ c + 2 n + 3の時間で解く別のkテープマ​​シンが存在することを述べています。ここでk  > 1です。 ^{[1] [2]} 元のマシンが非決定性である場合、新しいマシンも非決定性です。2 n + 3の定数 2 と 3 は 、たとえばn  + 2に下げることができます。 ^[1]

この構造は、元のマシンMの複数のテープ シンボルを新しいマシンNの 1 つのテープ シンボルにパックすることに基づいています。プロセッサでより長いワードとコマンドを使用するのと同様の効果があります。つまり、計算速度は上がりますが、マシンのサイズは大きくなります。新しいシンボルにパックされる古いシンボルの数は、必要な高速化によって異なります。

新しいマシンが 3 つの古いシンボルを 1 つの新しいシンボルにパックするとします。新しいマシンのアルファベットは次のようになります。これは、元のシンボルとパックされたシンボルで構成されます。新しいマシンには、同じ数のテープ(k > 1) があります。N の状態は次のコンポーネントで構成されます。 ${\displaystyle \Sigma \cup \Sigma ^{3}}$

• Mの状態;
• 各テープには、ヘッドの下のパック記号、左側のパック記号、右側のパック記号を説明する 3 つのパック記号があります。
• 各テープについて、 Nのヘッドの下のパックされたシンボル内の元のヘッド位置。

新しいマシンN は、与えられた入力を新しいアルファベットにエンコードすることから始めます (アルファベットに が含まれていなければならないのはそのためです)。たとえば、2 テープMへの入力が左側にある場合、エンコード後のNのテープ構成は右側のようになります。 ${\displaystyle \Sigma }$

新しいマシンは、3 つの古いシンボル (たとえば、空白のシンボル_、シンボルa、シンボルb ) を新しいシンボル (ここでは (_, a、b )) にパックし、最初のテープを消去しながら 2 番目のテープにコピーします。初期化の最後に、新しいマシンはヘッドを先頭に向けます。全体として、これには 2 n  + 3 ステップかかります。

初期化後、 Nの状態は です。ここで、 記号は、マシンによって後で埋められることを意味します。 記号は、元のマシンのヘッドがおよび内の最初の記号を指していることを意味します。ここで、マシンは6 つの独自の遷移を使用して、 Mのm  = 3 遷移のシミュレーションを開始します (この具体的なケースでは、速度は向上しませんが、一般にm は6 よりはるかに大きくなります)。MとNの構成を次のようにします。 ${\displaystyle (q_{0};~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])}$${\displaystyle ?}$${\displaystyle [1,1]}$${\displaystyle (\_,\_,\_)}$${\displaystyle (\_,a,b)}$

ここで、太字の記号はヘッドの位置を示します。Nの状態は です。次に次のことが起こります。 ${\displaystyle (q;~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])}$

• Nは右、左、左、右に動きます。4回の動きの後、マシンNはすべて満たされ、その状態は次のようになります。${\displaystyle ?}$${\displaystyle (q;~~~\#,(\_,\_,b),(b,a,b);~~~(b,a,b),(b,\_,\_),(\_,\_,\_);~~~[3,1])}$
• ここで、N は元のマシンのm = 3 の遷移に従ってシンボルと状態を更新します 。これには 2 つの移動 (現在のシンボルの更新と、隣接するシンボルの 1 つを更新) が必要になる場合があります。元のマシンが次のように移動すると仮定します (右側のNの対応する構成を使用)。

したがって、 Nの状態はになります。 ${\displaystyle (q';~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])}$

初期化には2 n  + 3ステップが必要です。シミュレーションでは、Nの6ステップがMのmステップをシミュレートします。m > 6 cを選択すると、実行時間は次のように制限されます。${\displaystyle f(n)/c+2n+3.}$

上記の定理は、1方向の読み取り専用入力テープと作業テープを備えたチューリングマシンにも当てはまります。^[3]${\displaystyle k\geq 1}$

シングルテープチューリングマシンの場合、線形高速化は実行時間が少なくとも のマシンで成立します。 時間のマシンでは成立しないことが証明されています。^[3]${\displaystyle n^{2}}$${\displaystyle t(n)\in \Omega (n\log n)\cap o(n^{2})}$

スピードアップ定理の証明は、アルファベットをより大きなものに置き換えることでストレージを圧縮する能力にかかっていることは明らかです。Geffert ^{[4]は、時間計算量の}非決定性単一テープチューリングマシンでは、アルファベットを増やすことなく線形のスピードアップを実現できること を示しました 。${\displaystyle T(n)\geq n^{2}}$

Regan ^{[5] は、}情報近傍と呼ばれる計算モデルの特性を考慮しました。この特性はメモリ構造に関連しています。チューリングマシンは線形近傍を持ちますが、コルモゴロフ-ウスペンスキーマシンやその他のポインタマシンは指数近傍を持ちます。Regan のテーゼは、線形高速化の存在は多項式情報近傍を持つことと関係があるというものです。この主張の重要な点は、指数近傍を持つモデルは、アルファベットの変更が許可されていても高速化がないということです (シンボルを格納する離散メモリを持つモデルの場合)。ただし、Regan はこの種の一般的な定理を証明していません。Hühne ^{[6] は、高速化をオンラインシミュレーションによって得ることを要求すると (通常のチューリングマシンでの高速化の場合)、}ツリーストレージを持つマシンでは線形高速化は存在しないことを証明しました。