7
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

$|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.

$\endgroup$
  • $\begingroup$ I think, this only works with this number of steps, if the machine can't make a "neutral" move (e.g. stay), too. Otherwise some more steps are needed (depending on the tape alphabet $\Gamma$). $\endgroup$ – frafl Apr 9 '13 at 15:15
  • 1
    $\begingroup$ @frafl: you are right (but the standard definition of Turing machine doesn't include the "stay", but only L / R). However - at this point - making a decider for that kind of TM can be a good exercise for the OP :-) $\endgroup$ – Vor Apr 9 '13 at 15:34
  • $\begingroup$ Thank you for your answer, but let me ask these too: 1) Is it always true that the machine will first scan the input to the end before doing anything(I mean isn't there any possibility that the machine will make a left before reaching the end of the input)? 2) This was the max number of steps to try out, how the machine can detect left move in each step? $\endgroup$ – msn Apr 27 '13 at 12:20
  • $\begingroup$ @mahdisaeedi: 1) no, it can make a left move during input scan; but if it makes a left move, your decider just stop simulating it and halt on YES. 2) the decider must simulate the target Turing machine on the input $w$ step by step; but as I wrote in the answer it is sufficient to simulate it for $|w|+N+1$ steps $\endgroup$ – Vor Apr 27 '13 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.