Log In
0 votes

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.

in Theory of Computation 96 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
L1:{<M> | there exist a Turing machine M' such that <M>$\neq$<M'> and L(M) = L(M')} How this problem becomes trivial? and if it non-trivial then please explain why is that so. According to my understanding, non-trivial properties are the one where a language ... and if it is then is it okay to say M1=M2 because they are kind of same machine but other one is just with some non deterministic nature.
asked Oct 30, 2018 in Theory of Computation Swapnil Naik 105 views
1 vote
0 answers
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 63 views
0 votes
0 answers
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language consisting of Turing ... any $TMs$. Prove that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 36 views