The Gateway to Computer Science Excellence
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 by Active (3.4k points) | 67 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
104,735 users