Let M be a Turing machine. Prove that it is decidable whether M, on a given input w, moves left at least 2021 times.

Question

I am pretty clear about the instance of the problem: If $M$ moves left at all is a decidable problem by simulating $M$ on $w$ for only $|Q|+|w|+1$ steps. where $Q$ is the states of the machine $M$. But for having $2021$ states will $|Q|+|w|+2021$ steps be applicable? because I think even if I have only one left move in these $|Q|+|w|+2021$ steps I can increase no. of steps to loop and get more left more. Where am I going wrong?

Answer 1

We simulate the TM, but only with a bounded tape: In our simulation, we include only $2021$ (initially empty) places to the left of the starting point, then the $|w|$ places of (originally) the input, and another $2021|Q|+1)$ (initially empty) places to the right. Such a limited simulation can be carried out without invoking the halting problem. The result may be one of

• The simulation attempts to leave the tape to the left
• The simulation attempts to leave the tape to the right
• The state of the simulation (tape, TM state, and position) repeats
• The simulated TM halts

If we simulated 2021 left moves bofore either of these happens, then the answer is clearly YES. So assume from now on that one of these four event happens before observing 2021 left moves. Actually, this cannot happen with the first event. In case of the fourth event, we completed the simulation and can aswer NO. In case of the third event, the machine must make (among others) a move left during the period. It follows that it will repeat indefinitely and make infinitely many left moves, so YES.

Remains the second event. The TM has entered "new territory" on the right more than $2021|Q|$ times, hence there is some state $q$ such that the TM "entered new territory while reaching state $q$" at least $2022$ times. Between these $2022$ times, there are $2021$ "gaps". As not so many moves left were observed, there is at leas tone gap in which no move left occurred. It follows that with state $q$ on an empty tape, the TM will move left (and stay in $q$) indefinitely. So the answer is NO.

Answer 2

Please check if this answer looks ok:

It is decidable, but not in $|Q|+|w|+2021$ steps.

Assumption: TM only moves left or right on reading any input, and doesn't stay at same place

---

Simpler Problem: TM moves left atleast once is decidable.

To Prove: We have to prove that if a TM does not move left in a finite number of steps then it never moves left.

The reason deciding whether TM moves left atleast once is decidable in time $|Q|+|w|+1$ time is the following. Considering a TM that does not make any left moves (ie. exactly 0 left moves) , then the TM can make at most $|w|$ moves right as it reads the TM (the states can be anything), after this, assuming it has never moved left, it starts seeing blanks.

Then there are at most |Q| unique tuples of (w=blank,state=$q_i$) tuples that the TM can go through, before it starts seeing repeats of states. On the $(|Q|+1)$'th step, it has to repeat a (w=blank,state=$q_i$) tuple by the pigeonhole principle.

Therefore whether the TM moves left or not is decidable in at most $|w| + |Q|+1$ moves. If in these many moves the TM (let's call it $M_1$), doesn't see a left move, it ends and says FALSE.

---

To answer the same question for 2021 left moves. One has to upperbound the number of moves the TM can make with at most 2020 left moves. One may guess that this is more than $|w| + |Q|+2021$ moves. This is because between the left moves there can be right moves.

1) Is the question decidable?

Yes. Use $M_1$ to decide whether one move left was made. If it returns TRUE, then switch $M_2$ to a new state such that it starts acting the same as $M_1$. This starts watching for the second move left. Recursively, $M_i$ starts watching the original TM - M, when $M_{i-1}$ says TRUE.

We can carry on like this with multiple machines (you can substitute tapes for machines also), until we see $M_{2021}$ saying TRUE, at which point M has made 2021 moves left.

2) How long does such a system have to watch M before deciding to say FALSE?

$M_1$ still has to wait for $|w|+|Q|+1$ time before it decides. Assume in the worst case, we are back at the left end of the tape. Then $M_2$ also takes $|w|+|Q|+1$ time. We can carry on this argument to say that in at most $2021(|w|+|Q|+1)$ the question is decidable, and if there are no 2021 left moves by this point, we return FALSE. Therefore we have a halting time given any input. So the problem is decidable.

Of course our bound of $2021(|w|+|Q|+1)$ was very weak.

3) Is it decidable in time $|w|+|Q|+2021$?

No (atleast not with this algorithm). Why? Say on for the first TM, $M_1$, we took $|w| + |Q|$ time, after which the first left move was made, then keep making $|w| + |Q|$ left moves (say $|w| + |Q|<2021$). Now $M_{|w|+|Q|}$ is operational. It keeps watching for $|w| + |Q|$ time. The total time taken so far is $3(|w| + |Q|)$ and $M_{|w|+|Q|}$ has still not decided (ie we have made only $|w|+|Q|$ left moves). Clearly the number of TM moves is not linear with coefficient 1 to the number of left moves we can decide. Therefore we take more than $|w|+|Q|+2021$ time to decide 2021 left moves.

*. Does this give us a tight upperbound?

Not entirely sure (I can't prove), but maybe, it takes $|Q|+|w| + 2(L)$ time to decide whether $L$ left moves have been made. in your case that would be $|Q|+|w| + 2(2021)$