Question 5.11: 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 during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
Let C = { 〈M〉 | M is a two-tape TM that writes a nonblank symbol on its second tape when it is run on some input}. Show that A_{TM} reduces to C. Assume for the sake of contradiction that TM R decides C. Construct a TM S that uses R to decide A_{TM}.
S = “On input 〈M,w〉:
1. Use M and w to construct the following two-tape TM T_{w}.
T_{w} =“On any input:
1. Simulate M on w 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_{w} ever writes a nonblank symbol on its second tape.
3. If R accepts, M accepts w, so accept . Otherwise, reject .”