対称チューリングマシン

対称チューリング マシンは、無向の構成グラフを持つチューリング マシンです(つまり、構成 i が構成 j を生成するのは、j が i を生成する場合のみです)。

正式には、 ⁠ ⁠ の${\displaystyle (p,ab,D,cd,q)}$形式の遷移のセットを持つチューリングマシンのバリアントを定義します。ここで、 p,qは状態、ab,cdはシンボルのペア、Dは方向です。Dが左 の場合、シンボルaの後に続くテープシンボルbの上の状態pにあるマシンのヘッドは、ヘッドを左に動かして状態をqに変更し、シンボルa,b をc,dに置き換えることで遷移できます。 ⁠ ⁠の逆の遷移も常に適用できます。Dが右 の場合、遷移は類似しています。2 つのシンボルを覗いて両方を同時に変更する機能は必須ではありませんが、定義を容易にします。 ${\displaystyle (q,cd,-D,ab,p)}$

このようなマシンは、1982年にHarry R. LewisとChristos Papadimitriou ^{[1] [2]}によって初めて定義されました。彼らは、無向グラフの2つの頂点s、tの間にパスがあるかどうかを尋ねる問題USTCONを配置するクラスを探していました。この時まで、非決定性を必要としないように見えたにもかかわらず、NLにのみ配置できました（非対称バリアントSTCONはNLに対して完全であることが知られていました）。対称チューリングマシンは、非決定性のパワーが制限されたチューリングマシンの一種であり、少なくとも決定性チューリングマシンと同等のパワーがあることが示され、その中間の興味深いケースを示しています。

⁠ ⁠ は、時間${\displaystyle {\mathsf {STIME}}(T(n))}$⁠ ⁠${\displaystyle O(T(n))}$で実行される対称チューリングマシンが受け入れる言語のクラスです。 ⁠ ⁠内の任意のマシンの非決定性を、一連の記号が非決定的に書き込まれ、その後に決定的な計算が続く初期段階に 制限することで、 ⁠ ⁠${\displaystyle {\mathsf {STIME}}(T)={\mathsf {NTIME}}(T)}$であることが簡単に証明できます。${\displaystyle {\mathsf {NTIME}}(T)}$

SSPACE (S( n ))は、空間⁠ ⁠${\displaystyle O(S(n))}$で実行される対称チューリングマシンが受け入れる言語のクラスであり、SL = SSPACE (log( n ))です。

SL は、USTCON に対数空間還元可能な問題のクラスとして同等に定義できます。Lewis と Papadimitriou は、定義により、USTCON の非決定性マシンを構築することでこれを示しました。このマシンは、同等の対称チューリング マシンの構築を可能にするのに十分な特性を備えています。次に、対称計算の特性から、グラフの無向エッジとして特別な構成を見ることができるため、SL のどの言語も USTCON に対数空間還元可能であることを観察しました。

2004年、オマー・ラインゴールドは、 USTCONを対数空間で実行する決定論的アルゴリズムを示してSL=Lであることを証明し、^[3] 2005年のグレース・マレー・ホッパー賞と（アヴィ・ウィグダーソンとサリル・ヴァダンと共同で）2009年のゲーデル賞を受賞した。証明では、ジグザグ積を使用して、エクスパンダーグラフを効率的に構築する。

• 講義ノート:CS369E: コンピュータサイエンスにおけるエクスパンダー Cynthia Dwork & Prahladh Harsha 著
• 講義ノート
• シャロン・ブルックナーの講義ノート
• 決定論的空間境界グラフ接続アルゴリズム Jesper Janson