The Gateway to Computer Science Excellence

+1 vote

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.

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.

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.

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.

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,473 answers

195,393 comments

100,368 users