Question 5.10: Consider the problem of determining whether a two-tape Turin...
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input w. Formulate this problem as a language and show that it is undecidable.
Let B = {〈M,w〉 | M is a two-tape TM that writes a nonblank symbol on its second tape when it is run on w}. Show that ATM reduces to B. Assume for the sake of contradiction that TM R decides B. Then construct a TM S that uses R to decide A_{TM}.
S = “On input 〈M,w〉:
1. Use M to construct the following two-tape TM T .
T = “On input x:
1. Simulate M on x using the first tape.
2. If the simulation shows that M accepts, write a nonblank symbol on the second tape.”
2. Run R on 〈T,w〉 to determine whether T on input w writes a nonblank symbol on its second tape.
3. If R accepts, M accepts w, so accept . Otherwise, reject .”