Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is a problem from my formal languages class

Consider the following problem: Determine if a Turing Machine M, on input w, will move its head to the left, at least once.

  1. Is this problem decidable?
  2. Can Rice's theorem be applied on this case?

and here is my attempt to answer (1):


Define M' as a turing machine that takes a pair (M,w) as input, where M is a turing machine encoded in some form recognized by M' and w is the input to M.

M' stops and accepts (M,w) whenever the head of the simulated machine M moves to the left while processing input w

For a particular input to M' (M,w), construct the turing machine P as follows:

  • P executes M' on (M,w)
  • P stops and accepts any input if M' accepts (M,w)

We have reduced the Universal Turing Machine U to P. Since we know that L(U) is not decidable, we conclude that L(P) is not decidable. Consequently, M' is not decidable


As to the applicability of Rice's theorem, I'm not sure...

"Any nontrivial property about the language recognized by a Turing machine is undecidable"

moving the head of the machine is not a property of the language itself, it is a property of the machine...

thoughts, please?

Thanks!

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

Your idea that Rice's theorem is inapplicable is correct. For the theorem to hold, we want to have whenever $L(M_1)=L(M_2)$, $M_1$ satisfies the property iff $M_2%$ does. This is evidently not true of the property presently under consideration. Think of two machines identifying a regular language (i.e. recognizable in a single pass), but one machine backs up all the way to the left, while the other does not.

But your reduction does not make sense. At a very high level, the point of a reduction is something like: "I know problem $P_1$ is hard. If I could solve problem $P_2$, voila! Here is a method to solve problem $P_1$. But this should not be possible. Therefore, $P_2$ has to be hard." Typically, $P_1$ is the halting problem, and you want $P_2$ to be the "left-mover" problem. So, given an instance of the halting problem, you manufacture an instance of the left-mover problem. If I read your reduction correctly, you're doing it in the opposite direction.

Now, something else is wrong with your solution. The problem is decidable! Here is the algorithm sketch: observe that if $M$ never moves left on $w$, it is making a single pass on the string. Eventually, $M$ finishes reading $w$ (which is of finite length), and starts reading spaces. Now, you simply look at which state $q$ $M$ is in when it finishes reading $w$, and look at the subgraph of states it visits on reading spaces. None of these should ever involve moving to the left.

share|improve this answer
    
Totally makes sense now. Big thanks! –  marcos Jun 11 '12 at 4:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.