How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable?

Intuitively speaking I think it is indeed undecidable because there seems to be no limit to the possible configurations, however I am not sure.

Thanks a lot in advance!

  • $\begingroup$ 1) Is M a TM that moves the head only to the left or to the right in every transition? Or it also has the option of not moving the head at all? 2) It should be "while running on the input w", right? $\endgroup$ Jan 8 at 17:25
  • $\begingroup$ No it does not have the option of not moving the head at all, and yes while running on w $\endgroup$
    – Joey
    Jan 8 at 17:26

If $M$ does not have the option to not move its head at all, as stated in a comment to the question, then the problem is trivially decidable by the Turing machine that immediately halts and accepts.

If $M$ might not move its head while computing $T(w)$ and the problem is to decide whether it actually does so, then the problem must be undecidable as otherwise the halting problem would also be decidable.

To see this, construct a Turing machine $M'$ that simulates $M$ while always moving its head. When the simulation terminates, $M'$ keeps its head in place for one more step, and then halts. It is not hard to come up with an algorithm that builds $M'$ from $M$, thus showing that $M'$ is computable. Then $\langle M', w \rangle \in L$ if and only if $M$ does not halt.

  • $\begingroup$ Thats what I initially thought. Please note that $M$ may not move its head when it is in the leftmost cell and the transitions that it takes suggests to move the head to the left. Right? I wrote an answer due to this case! $\endgroup$ Jan 8 at 18:16
  • $\begingroup$ You are assuming that the tape of $M$ is only infinite in one direction. Usually I have seen TMs defined with infinite tape in both directions. See e.g., "Introduction to Automata Theory, Languages, and Computation " by Hopcroft and Ullman that writes "Initially the input which is a finite length string of symbols chosen from the input alphabet is placed on the tape. All other tape cells extending infinitely to the left and right initially hold a special symbol called the blank". $\endgroup$
    – Steven
    Jan 8 at 18:18
  • $\begingroup$ I see what you mean. The question is unclear then. $\endgroup$ Jan 8 at 18:19
  • $\begingroup$ Thank you very very much for your answers. The tape of M is indeed infinite in both directions, however I fail to see how in the case that M does not move its head in every step while computing w that this means that M also halts. $\endgroup$
    – Joey
    Jan 9 at 16:21
  • $\begingroup$ I see that you are assuming in the beginning already upon input w that M' simulates M while always moving its head, in that case what happens when M doesn't move its head in every step while computing input w? $\endgroup$
    – Joey
    Jan 9 at 16:23

Edit: the answer assumes that the tape of a TM is left bounded, that is, the tape has a leftmost cell.

Given $\langle M, w\rangle$, $M$ does not move its head while running on the input $w$ when its in never the case that the head of $M$ is at the leftmost and the next transition suggests that $M$ moves its head to the left. Now can we decide whether this situation happens? Intuitively, the answer is no as $M$ may not halt on $w$ and this situation may not happen at all, in this case we can never know whether it will happen in the future or not, so we keep waiting. This smells like the halting problem.

Formally, we reduce the complement of the halting problem to your problem. For input $\langle M, w\rangle$, the reduction outputs $\langle K, w\rangle$, where $K$ is a machine that operates as follows. Given input $x$ for $K$, $K$ writes $\#x$ on its tape (where $\#$ is a special letter) without moving to the left while it is in it leftmost cell. Then, $K$ moves its head to the first letter after $\#$, moves to the initial state of $M$, and runs on $x$ in the same $w$ that $M$ runs on $w$ with the following differences:

1- Whenever $K$ reads $\#$ it stays in the same state of $M$ and moves to the right without modifying the tape. (Note that $\#$ simulates the leftmost cell of $M$'s tape).

2- Instead of moving to the rejecting or accepting state of $M$, $K$ goes to a special state where it gets stuck and keeps going to the left without modifying its tape.

If $M$ does not halt on $w$, then $K$ does not halt on $w$, however by the way $K$ works, it moves its head in every transition (it always moves to the right when it is in the leftmost cell). Conversely, if $M$ halts on $w$, then eventually, $K$ gets stuck in the leftmost cell, in particular, it does not move its head in every step while running on $w$.


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.