Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In writing a decider for a machine to see if it has made a left move or not on an input of w, it is said that if we continue the computation for $|w|+N+1$ ($N$ : number of states) number of steps, we can make a decision for this decide.
I didn't get why $|w|+N+1$ number of steps. Could someone explain this in more detail?
$|w|$ steps are needed to scan the input, if a left move is made during this scan accept.
Otherwise, at the end of the input, the head of the Turing machine is on the blank part of the tape (over the first blank symbol after the input). Suppose the state is $q_{i_1}$. If the Turing machine doesn't make a left step and stays on state $q_{i_1}$, then it will do it forever (it will continue moving right on the infinite blank tape on state $q_{i_1}$). But it can move right and switch to state $q_{i_2}, i_1 \neq i_2$.
If you continue with this reasoning you see that there are only two possibilities:
it moves left or
it enters a state $q_{i_{k+j}}$ for the second time and thus it will loop forever: $q_{i_k} \rightarrow q_{i_{k+1}}\rightarrow ...\rightarrow q_{i_{k+j}}=q_{i_k} \rightarrow q_{i_{k+1}}\rightarrow ...$
But there are only $N$ different states so at most $N+1$ more steps are needed to detect such loop.
