7. (12 pts.) Determine whether the following decision problems are decidable or undecidable: (a) Given a TM T, does it ever reach a state other than its initial state if it starts with a blank tape? Tip: Imagine that you run T on a blank tape. Under what circumstances could you answer the question in the problem? What can happen if the tape head n left or right? What if it moves left? What if it moves right? Note: Describe how in each possibility you can answer the question in the problem, thereby showing that the problem is decidable. (b) Given a TM T, does T eventually enter every one of its nonhalting states if it begins with a blank tape? Tip: Pretend that one of the nonhalting states is actually the only accepting state. If we could decide this question, it would be almost equivalent to be able to decide whether T accepts A, but that problem is undecidable. So try to reduce Accepts-A to this problem. Given a TM, modify it to get a new TM that will enter all its nonhalting states exactly if the original TM accepts A. How can you make sure that the new machine does not enter all nonhalting states if the original TM does not accept A? How can you make sure that the new machine does enter all nonhalting states if it does? Note: Reduce Accepts-A to this problem, i.e. given a TM T, explain how to create a TM T' such that T accepts A iff T' eventually enters every one of its nonhalting states if it begins with a blank tape. Explain the construction of T' and justify why the claimed equivalence holds. 7. (12 pts.) Determine whether the following decision problems are decidable or undecidable: (a) Given a TM T, does it ever reach a state other than its initial state if it starts with a blank tape? Tip: Imagine that you run T on a blank tape. Under what circumstances could you answer the question in the problem? What can happen if the tape head n left or right? What if it moves left? What if it moves right? Note: Describe how in each possibility you can answer the question in the problem, thereby showing that the problem is decidable. (b) Given a TM T, does T eventually enter every one of its nonhalting states if it begins with a blank tape? Tip: Pretend that one of the nonhalting states is actually the only accepting state. If we could decide this question, it would be almost equivalent to be able to decide whether T accepts A, but that problem is undecidable. So try to reduce Accepts-A to this problem. Given a TM, modify it to get a new TM that will enter all its nonhalting states exactly if the original TM accepts A. How can you make sure that the new machine does not enter all nonhalting states if the original TM does not accept A? How can you make sure that the new machine does enter all nonhalting states if it does? Note: Reduce Accepts-A to this problem, i.e. given a TM T, explain how to create a TM T' such that T accepts A iff T' eventually enters every one of its nonhalting states if it begins with a blank tape. Explain the construction of T' and justify why the claimed equivalence holds