Question

Which of the following problems about Turing machines are solvable, and which are undecidable? Explain your answers carefully.

(a) To determine, given a Turing machine M, a state q, and a string w, whether M ever reaches state q when started with input w from its initial state.

(b) To determine, given a Turing machine M and a symbol a, whether M ever writes the symbol a when started with the empty tape.

Answer 1

(a)

This problem is undecidable means not solvable. Suppose it were solvable; then some machine G would
solve it. But given M and w, we could feed (M, w, h) ot G, where h is the halting state of M;
if more than one, we can simply repeat our query several times, and return G’s answer, and this
would constitute an effective procedure for deciding the halting problem.

(b)

Not solvable

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