In theoretical computer science, a crossing sequence at boundary i, denoted as C i ( x ) {\displaystyle {\mathcal {C}}_{i}(x)} or sometimes c s ( x , i ) {\displaystyle cs(x,i)} , is the sequence of states q i 1 , q i 2 , . . . , q i k , {\displaystyle q_{i_{1}},q_{i_{2}},...,q_{i_{k}},} 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.