Neha Patil (Editor)

Crossing sequence (Turing machines)

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In theoretical computer science, a crossing sequence at boundary i, denoted as C i ( x ) or sometimes c s ( 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.


Crossing sequence (Turing machines) Wikipedia

Similar Topics
Rifat Atun
Per Hannevold
Agnieszka Holland