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!
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.
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$.
