Michael Sipser Edition 3 Exercise 5 Question 15 (Page No. 240)

Question

Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate this problem as a language and show that it is decidable.

Comments

https://math.stackexchange.com/questions/156788/determine-if-a-turing-machine-m-on-input-w-will-move-its-head-to-the-left-at
In the above link also, he has mentioned the same thing that the string is finite so it will finish reading string.
But according to me, if we don't know the language then it can be Recursively Enumerable and if the string w is not in the language then Machine M will not finish reading w. ( and the reason for this is that other machines like pda and fa depend on characters of the string only to move forward [i.e. at every state they will check the character of the string to decide where to go] but Turing Machine reads from string as well as the tape, therefore, it can go in loop just after reading the first character as there are operations like X,X,R ).

So, this problem should be undecidable if the language is recursively enumerable, and decidable if the language is recursive but not RE.

 

---

Yes, I was wrong earlier, I did not study the subject properly.

So, let me make a couple of assumptions.

1. $w$ is a string of finite length, so $|w| < \infty$

2. $w$ is a string of a language over finite alphabets, so $w \in \Sigma^{*}_{(a,b)}$

Now,

let me define the problem as

$L = \{<M, w> | \text{M is a TM and M halts on turning it's head left at least once during it's computation on } w, w \in \Sigma^*\}$

So, we can construct a decider as

1. Simulate $w$ on $M$

2. If $M$ turns it's head left, accept and accept.

3. Now, it might happens that the machine never turns left, in this case, we have following options -

    (a) on reading current input alphabet $a,b$,  machine goes right.

    (b) machine has finished reading the input $w$, so it reads blank symbol $\$ \not \in \Sigma^*$, from the tape and moves right.

4. So, even if the machine is non-halting, it's state-transition diagram has finite transitions.

 it repeats one of the above (a) or (b), which could be detected in at most $2 \cdot |w|$ steps which means we have a cycle in the state transition diagram.

This is where my assumptions come into picture.

If the input symbols were not finite, then I could have mapped them to natural numbers and then I could have had a machine that on reading a symbol, writes a random alphabet and goes right. Then I won't be able to tell if the machine is repeating the state or not.

If the length of the string was infinite, then well, I'll never be able to reject the string.

5. So, I can reject the string after finite number of steps.

Hence the $L$ is decidable.

---

Now, the problem @Arjun asked, 

$L = \{<M> | \text{M accepts string 'aaa'}\}$

I vastly misinterpreted the question as, "is there a Turing machine that accepts / reject aaa". 

Later, I realized that the input to the decider is not the "string aaa" but encoding of a Turing machine $M$.

Now this problem is undecidable, because the machine can have infinite different configurations, e.g. on seeing input symbol 'a', go to any random place, write 1 there, come back. (Earlier, machine couldnt do this, cause it could go only right, not left). These transitions are not repeating, and the turing machine will not loop, neither will it halt, and hence, we can't reject the string, but we can accept.

Or, it may accept a string right after we say it rejects after checking a finite number of steps. Hence undecidable.