Turing machine accepts any word

Question

Let M be a Turing-machine with tape alphabet = {0, 1} that does not move beyond the first 64 cells of its tape. Is the problem "Does M accept any word?" decidable?

1. I would say it does not accept any word because we can have words longer than 64 characters.
2. I would say it does because if it accepts any word, we don't care about the length. It always goes into accepting state.

Can someone please explain this to me?

Answer 1

Let $P = \{ w \in \{ 0,1 \} \mid |w| \le 64 \land w \in L(M) \}$. Since $P$ contains only words over an alphabet (i.e., a finite set) and all words in $P$ have bounded length, $P$ is finite. Moreover, any word $w \in \{0,1\}^\ast$ with length $|w| > 64$ is in $L(M)$ if and only if there is a prefix of $w$ which is in $P$. Thus, to decide $L(M)$, we only need to check whether the input has a prefix out of finitely many possibilities (i.e., those in $P$).

Hence, $L(M)$ is not only decidable, it is decidable in constant time.

Note this construction does not require any knowledge of $M$ whatsoever (in particular, there is no need to simulate $M$). We only need to show the existence of a TM which decides $L(M)$, not actually construct one.