Crossing sequence (Turing machines)

In theoretical computer science, a crossing sequence at boundary i, denoted as $\mathcal{C}_i(x)$ or sometimes $cs(x,i)$ , is the sequence of states $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.

References

This article is issued from Wikipedia - version of the 12/17/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.