patternMinor
Deciding if a Turing machine has made a left move
Viewed 0 times
leftmademovehasdecidingmachineturing
Problem
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?
I didn't get why $|w|+N+1$ number of steps. Could someone explain this in more detail?
Solution
$|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.
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.
Context
StackExchange Computer Science Q#11159, answer score: 9
Revisions (0)
No revisions yet.