Is it decidable whether a given Turing machine moves its head more than 481 cells away from the left-end marker, on input ε?

Question

So, while reading some problems on decidability, I came across the following resource: https://www.isical.ac.in/~ansuman/flat2018/tm-more-undecidable.pdf

Here, on page no 12, it is written that the problem is decidable and with the following argument:

"Yes, Simulate M on for upto m^481 · 482 · k steps. If M visits the 482nd cell, accept, else reject."

I am quite confused with the step count. Can anyone please explain what does this mean, or maybe point to some resources where I can find a proper explanation!!!! Image of the slide

Answer 1

A run of a TM is a sequence of configurations, where each configuration states the contents of the tape (from the left marker, up until the point where it is blank all the way to the right), the location of the head, and the state.

An important feature of (deterministic) TMs is that you can uniquely continue a run from a given configuration. That is, a configuration has all the information you need to proceed.

In particular, if a configuration $c$ yields a runs that gets back to $c$, at some point, then the run is stuck in a loop (note that this is not a necessary condition, a run might not halt while never repeating a configuration!).

Now, consider all the possible configurations that use up to 481 cells. There is a finite amount of those, namely $m^{481} \cdot 482 \cdot k$ (where $m$ is the size of the alphabet, and $k$ is the number of states).

Thus, if you simulate the run for that many steps, then either at some point the machine goes beyond 481 cells, in which case you accept, or it doesn't, in which case you know for sure that a configuration must repeat (by the pigeonhole principle), so you can reject.