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

I can tell that this is decidable because the string to check is always finite. Therefore, we will just run the turing machine for the whole string. And when the string ends we will get the answer whether the turing machine M ever attempts to move its head left or not.

---

So, the problem of deciding if a TM will accept a string "aaa" is __________?

---

OK. I AM CONFUSED.

If we know that language L given is Recursively Enumerable and we have to find whether string w belongs to L or not?

This is undecidable because if the string w does not belong to L then TM will never halt.

Here, I don't know WHY will the TM not halt, even if the string is FINITE.

PS: According to this the answer to both of the above questions should also be undecidable.

---

@nadeshseen all FINITE languages have a FSM. So, a TM will halt on every finite language.

So, the problem of deciding if TM will accept a string "aaa" is decidable. 

 

---

@toxicdesire Then how is TM accepting problem undecidable?

---

I am talking about RE languages where Language is countable but infinite.
In this also every string will be finite, but TM will not halt for cases where the string is not the part of the language.

---

@Arjun I'm not sure if I'm right but my reasoning is this - 

the halting problem is if TM halts on any arbitrary input. 

now, input here means a language, i.e. a set of strings. So it can be finite / infinite. 

Now "any arbitrary input" doesn't tell anything about "finite/infinite", so worst case we need to check by running TM on every input. If it's finite, we will accept otherwise we roll forever. Hence undecidable. 

Now here you've given explicitly that the language is finite. So, decidable. 

Is it on the right track or I'm misunderstanding big time?

---

@toxicdesire input is a string not a language in halting problem.

What you are talking about is similar to finiteness problem(whether a language is finite or not) 

---

@nadeshseen

source ?

---

@toxicdesire https://www.cs.odu.edu/~toida/nerzic/390teched/computability/unsolv-1.html

---

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.