Solved

# Formulate Turing Machine.

Posted on 2011-04-27

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.