Given a Turing machine M a string w and a symbol x, determine whether M
writes symbol x on the tape during the computation on input string w. Hint: use a similar reduction as in the state-entry problem which we described in class.
My solution is:
L={<M>|M is a TM and M prints the symbol x on its tape}.
1) Assume that is decidable and R is the decider.
2) Then we can use R and construct a TM S to decide the halting
problem.
S="On input <M,w>, where M is a TM and w is a string:
1. Construct M1 such that M1 writes a special symbol on the tape,
say symbol #, if and only if the machine halts. We choose the special
symbol # to be different from any other symbol written on the tape.
We can easily construct machine M1 as follows. Machine M1 is
identical to machine M. The only difference is that in M1 we add
transitions from every halting state of M to a new state, and in
these transitions we write the symbol # on the tape.
2. Run R on <M1,w,#>.
3. If R accepts, accept; if it rejects, reject.
3) But the halting problem is not decidable therefore R cannot exists.
Is it a right proof? Thanks.
www.cs.rpi.edu/~drinep/modcomp/class20.ppt
So you should reduce the halting problem to your problem. This appears to be what you tried to do, but why use # instead of x?