交差シーケンス（チューリングマシン）

理論計算機科学において、境界iでの交差シーケンスは、または と表記され、入力 x に対するチューリングマシンの状態のシーケンスであり、この状態シーケンスでは、ヘッドがセルiとi + 1 の間を交差します (最初の交差は常に右交差であり、次の交差は左交差、などであることに注意してください)。 ${\displaystyle {\mathcal {C}}_{i}(x)}$${\displaystyle cs(x,i)}$${\displaystyle q_{i_{1}},q_{i_{2}},...,q_{i_{k}},}$

場合によっては、交差シーケンスは、状態、テープの内容、ヘッドの位置という 3 つの要素を表す 構成のシーケンスとして考えられます。

交差シーケンスの研究は、例えば計算複雑性理論で行われます。