1
$\begingroup$

I came across below problem in this pdf:

Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.

Solution given is as follows:

Let the machine only writes blank symbol. Then its number of configurations in the com computation on w is q × 2, where q is the number of states of M; the factor 2 is for the choices re. the direction of heads movement; there is no factor for the written symbol because that is always blank. So the problem is decidable, decided by the following machine: input (M,w), run M on w for q × 2 steps; if it M ever writes a non blank symbol, stop with yes answer; if M never writes a non blank symbol, stop with no answer

Doubts:

Q1. How be sure all q x 2 configurations will happen while running q x 2 steps on w? Some configuration may get repeated in q x 2 steps.

Q2. Question says "when started on the empty tape", but the answer tried to simulate TM on non empty string w. How does it makes sense?

$\endgroup$
1
$\begingroup$

Q1: A state can get repeated. The point is that if a state gets repeated and no non-empty symbol has even been written, then you known the that the Turing machine will never halt as it is necessarily stuck cycling through some of the states encountered so far. Since none of the states of the cycle caused the TM to write a non-blank symbol, the TM will never write a non-blank symbol.

After $2q$ steps, either a non-blank symbol has been written, and you can answer "yes", or all the written symbols were blank and (at least) one state must have been encountered two or more times, meaning that you can answer "no".

Q2: My guess is that $w$ is defined somewhere to be the empty string. If the TM can be started with some arbitrary string $w$, then a variation of the above solution still works. Suppose that the head of the TM starts at the beginning of $w$. The number of states increases by a factor of at most $1+|w|$ in order to take into account all possible states of the tape (if only blank symbols are written, then the tape always contains one of the $1+|w|$ suffixes of $w$). If the head can start anywhere then this factor will be at most $1+|w|^2$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In Q1. Do you mean "either a non-blank symbol has been written, and you can answer yes... and you can answer no"? Because question asks "whether M ever writes a non blank symbol". In Q2. Didnt get "in the number of states corresponding to the number of subsets of positions of w that have been overwritten by a blank symbol" $\endgroup$ – anir Nov 26 '19 at 5:27
  • $\begingroup$ You are right. I fixed my answer. I also clarified the latter part. $\endgroup$ – Steven Nov 26 '19 at 8:34

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.