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


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?


1 Answer 1


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$.

  • $\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$
    – RajS
    Nov 26, 2019 at 5:27
  • $\begingroup$ You are right. I fixed my answer. I also clarified the latter part. $\endgroup$
    – Steven
    Nov 26, 2019 at 8:34
  • $\begingroup$ @Steven ""Turing machine print some non blank character ""-- is decidable. But by your same logic why ""Turing machine print some arbitrary output is undecidable""? What is the difference between two? $\endgroup$
    – A. H.
    Jul 17, 2022 at 12:57
  • $\begingroup$ The difference between the two is the state of the tape. If a Turing machine never prints a non-blank character and the tape is initially empty then the tape is always in the same state (notice that the position of the head doesn't matter), and hence the Turing machine has a whole can only be in finitely many global states. In contrast, if the Turing machine is allowed full access to the tape, then it can be in infinitely many global states. $\endgroup$
    – Steven
    Jul 17, 2022 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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