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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,258 answers

198,086 comments

104,735 users