1
$\begingroup$
  1. If a Turing Machine M, on input w, will M ever move its read/write head to the left?
  2. Determine if this violates Rice's Theorem.

1. I think the answer for Q1 is decidable because we can make a Turing Machine that decides the problem as follows:

Step 1: If M halts on w and it never moved left, reject it.

Step 2: If M ever moves left, halt and accept.

Step 3: If M loops forever (some configuration repeats) then reject it

Step 4: Otherwise, reject (M moves right, eventually encounters a blank symbol, and moves right forever, which means that M will never move left. So, reject it.)

2. We proved that for some language L L(M) is decidable. So, we can say that L(M) is Turing-recognizable. The property 'L(M) is Turing-recognizable' is trivial because there does not exist a Turing-recognizable L2 such that L2 does not belong to L. Thus, our problem is decidable with the following decider:

"Step 2: If M ever moves left, halt and accept."

, and this does not violate Rice's Theorem.

$\endgroup$
1
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Apr 8 at 20:20
7
$\begingroup$

I'm afraid that your logic doesn't make sense, since you can't implement Step 1. In order to implement it, you'll have to run $M$ and see if it every halts, but this is impossible, since it's the halting problem.

Nevertheless, the problem is decidable. The details of this argument depend on the exact Turing machine model, but in order to illustrate the basic idea, it suffices to consider the simplest possible model, in which there is only one head, and at each step, it has to move (either one step to the left, or one step to the right). We simulate $M$ for $|w|$ steps. Either it has moved to the left (in which case we know the answer), or otherwise, it has gone past the input.

In the latter case, suppose that the Turing machine is at some state $q$ after $|w|$ steps. Let's say that a state is bad if when $M$ reaches it, if the input under the head is blank, then it moves left. Construct a directed graph in which there is an arrow from $q$ to $p$ if $M$ transitions from $q$ to $p$ when the input under the head is blank. There are three cases:

  • The path starting at $q$ reaches a bad state. In this case the head of $M$ will eventually move left.
  • The path starting at $q$ reaches a halting state or closes a cycle, in both cases not going through a bad state. In this case the head of $M$ will never move left.

This shows how to decide whether $M$ every moves left upon reading $w$.


This might seem to contradict Rice's theorem, but it doesn't. The reason is not what you state — the problem is not trivial: there are pairs $(M,w)$ for which $M$ does move left when running on $w$, and there are other pairs when this doesn't happen. Rather, the property of never moving left is a syntactic property rather than a semantic property: it depends on the Turing machine $M$ instead of on its language $L(M)$.

$\endgroup$
15
  • $\begingroup$ Thank you for your prompt reply! $\endgroup$
    – Juns
    Apr 8 at 10:47
  • $\begingroup$ Case 1: If M has moved to the left during its computation then we accept it. Case 2: If M has gone past the input, we should check what content is under the head at the end of its computation. Case 2-1: If the input under the head is blank, the head of M will eventually move left. So, we accept it. Case 2-2: If the input under the head reaches a halting state or closes a cycle, the head of M will never move left. So, we reject it. $\endgroup$
    – Juns
    Apr 8 at 10:53
  • $\begingroup$ Am I understanding your logic correctly? $\endgroup$
    – Juns
    Apr 8 at 10:53
  • 1
    $\begingroup$ I'm afraid not. I think my answer is verbose enough. I'll let you work it out. $\endgroup$ Apr 8 at 10:54
  • $\begingroup$ In every situation, if the input under the head is blank, then will it move left? Isn't the machine supposed to move to the right if it encounters a blank symbol? $\endgroup$
    – Juns
    Apr 8 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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