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.
- Is this problem decidable?
- 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...