Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 437
  • Last Modified:

Formulate Turing Machine.

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.
0
Mr_Lee
Asked:
Mr_Lee
  • 3
2 Solutions
 
TommySzalapskiCommented:
This shows the undecidability of the state entry problem
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?
0
 
Mr_LeeAuthor Commented:
I thought that I can implicitly understand "symbol" x is anything, and # is one of the thing. I thought x can be @, or !, or so on.
0
 
TommySzalapskiCommented:
Oh I see. I took it literally to mean x. Yes then. I agree with your proof.
0
 
TommySzalapskiCommented:
I would use the same name x when writing the proof though so it's clear.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now