# Turing machine accepts any word

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?

• What is the bandwidth of a Turing machine? Is it the same as space? – Yuval Filmus Mar 24 at 19:18
• @YuvalFilmus Yes, bandwith and space is the same. – AndiCover Mar 24 at 19:28
• How exactly do you measure space? How many tapes does your machine have? – Yuval Filmus Mar 24 at 19:30
• Double check. This doesn’t make sense, since the input could be arbitrarily long. – Yuval Filmus Mar 24 at 19:33
• Can you copy and paste the full text of the original problem? Can you add a reference to the place where you saws the original problem? Please read carefully the definition of a Turing machine. – Apass.Jack Mar 24 at 21:13

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.