While studying for an up-and-coming exam, I stumbled upon the following question:
$$ L=\{\langle M \rangle,\langle w\rangle:M\text{ is single-tape and }M \text{ running on }w \text{ doesn't go over the first }|w|+1 \text{ cells} \} $$
True or False: $L\in$$RE\setminus$$R$
The answer is false, since $L\in$$R$. The explanation was that you could write a TM $D$ that works for $(|Q|+|\Gamma|)^{|w|+2}$ steps. If during this number of steps $D$ went over the first $|w|+1$ cells, it rejects, and accepts otherwise.
I couldn't for the life of me figure out why that bound was chosen.
Any insight on the matter will be greatly appreciated.
$(|Q|+|\Gamma|)^{|w|+2}$ is just a crude estimate of the number of possible configurations the machine can be in without having left the first $|w|+1$ cells.
I'm assuming that $Q$ is the set of machine states and $\Gamma$ is the tape alphabet (it may be the other way around, but that doesn't matter).
In order to count configurations, we need to ask ourselves how we can describe a configuration. Clearly we need to tell what the contents of the tape is, which is a string of $|w|+1$ elements of $\Gamma$. But we also need to say where in the tape the machine is currently located, and which state it is in. Suppose we indicate that by writing the current state of the machine just to the left of the symbol currently being scanned. (This assumes that $Q$ and $\Gamma$ are disjoint, which can easily be arranged, or just imagined).
But that means that we now have a string of $|w|+2$ symbols taken from $Q\cup\Gamma$. Most such strings are not valid configurations, however: to be a configuration there must be exactly one symbol from $Q$ and the rest must be from $\Gamma$. But for the purposes at hand it doesn't matter whether we get too high a count -- the important thing is that we get a finite (and computable) one. So for simiplicity we'll just count the non-configuration strings anyway. And then the total number of strings we're considering is $|Q\uplus \Gamma|^{|w|+2}$.
A tighter estimate would be $|\Gamma|^{|w|+1}\cdot |Q| \cdot (|w|+1) $, but that takes more space to write, and doesn't really matter when we're only after an existence proof.