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 Wednesday, December 17, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.