1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What is the bandwidth of a Turing machine? Is it the same as space? $\endgroup$ – Yuval Filmus Mar 24 at 19:18
  • $\begingroup$ @YuvalFilmus Yes, bandwith and space is the same. $\endgroup$ – AndiCover Mar 24 at 19:28
  • $\begingroup$ How exactly do you measure space? How many tapes does your machine have? $\endgroup$ – Yuval Filmus Mar 24 at 19:30
  • 2
    $\begingroup$ Double check. This doesn’t make sense, since the input could be arbitrarily long. $\endgroup$ – Yuval Filmus Mar 24 at 19:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Mar 24 at 21:13
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.