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

1 vote
211 views
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.
0
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.
1
So, the problem of deciding if a TM will accept a string "aaa" is __________?
0
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.
0

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

1

@toxicdesire Then how is TM accepting problem undecidable?

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

@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?

1

@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)

0

source ?

0

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.

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