Crossing sequence (Turing machines)

In theoretical computer science, a crossing sequence at boundary i, denoted as [math]\displaystyle{ \mathcal{C}_i(x) }[/math] or sometimes [math]\displaystyle{ cs(x,i) }[/math], is the sequence of states [math]\displaystyle{ q_{i_1},q_{i_2},...,q_{i_k}, }[/math] of a Turing machine on input x, such that in this sequence of states, the head crosses between cell i and i + 1 (note that the first crossing is always a right crossing, and the next left, and so on...)

Sometimes, crossing sequence is considered as the sequence of configurations, which represent the three elements: the states, the contents of the tapes and the positions of the heads.

Study of crossing sequences is carried out, e.g., in computational complexity theory.