Writes Non Blank: Given a turing machine T, does it ever writes a non-blank symbol on its tape, when started with a blank tape.
how the above problem is solvable?
somewhere i got this explanation:
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.
why is it that q*2 is taken as an upper bound for writing a non blank symbol? there can be some machine which can write non blank on more than q*2 moves.
in fact we can apply rice's theorem here.. as this is a non-trivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
