a. Hand in this examination as the first page to your solutions. b. Do not answer more than 6 question. c. The acronym TM is for Turing machine. d. Clearly state your answer to the problem in the first line of your solution. Consider a 2-tape TM with number n represented by 1^n on the first tape and m represented by 1^m on the second tape. Assuming the read-write heads of both tapes are positioned at the beginning of both tapes, program the TM to accept the input if n - M is a TM and M accepts the string 000}. Show L is undecidable. Please answer ONLY 4 of questions 3 through 8. Prove or disprove: If L_1 is decidable and L_2 is recognizable but not decidable then L_1 union L_2 is decidable. Let T be the set of TMs and let 2^T be the power set of T. Prove that T is uncountable. Prove or disprove: If L is recognizable over sigma then sigma* - L must also be recognizable. Let L = { - M is a TM and M accepts the string 000}. Show sigma* - L is unrecognizable. You are given a list of dinner guests and a list of pairs of guests who can be seated next to each other. The problem is to arrange the guests around the table so that if two guests are seated next to each other then they are in the list of pairs. Give a polynomial time reduction from a known NP-Complete problem to the problem above. Consider A2_Tm which is a variation of A_Tm where the pairs only include special TMs. These TMs all have the property that they ALWAYS halt on strings beginning with 0, and they NEVER halt on strings beginning with 1. Is A2_Tm decidable