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.
in Theory of Computation by Veteran (54.8k points) | 34 views
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 __________?

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) 



source ?

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.


Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,473 answers
100,368 users