Problem 4. Combining TM programs Suppose you are given two TM programs for the TM simulator, Ml and M2. You have access to these programs but you know nothing about what these machines do, except that Ml decides some language L1, and the second decides L2. a) Can you use M1 and M2 to create a new program that will decide L1 u L2? If so, describe how. b) Can you use M1 and M2 to create a new program that will decide L1 n L2? If so, c) Can you use M1 to create a new program that will decide the complement of L1? If so, d) Based on your work above, what conclusions can you draw? Justify your answer using describe how. describe how definitions Hint: the word "closed" should appear in your answer. e) What if we replaced the word "decide" by the word '"recognize" throughout this problem? Would your answers to (a), (b), (c) be the same? What would be your conclusion in (d)? Problem 4. Combining TM programs Suppose you are given two TM programs for the TM simulator, Ml and M2. You have access to these programs but you know nothing about what these machines do, except that Ml decides some language L1, and the second decides L2. a) Can you use M1 and M2 to create a new program that will decide L1 u L2? If so, describe how. b) Can you use M1 and M2 to create a new program that will decide L1 n L2? If so, c) Can you use M1 to create a new program that will decide the complement of L1? If so, d) Based on your work above, what conclusions can you draw? Justify your answer using describe how. describe how definitions Hint: the word "closed" should appear in your answer. e) What if we replaced the word "decide" by the word '"recognize" throughout this problem? Would your answers to (a), (b), (c) be the same? What would be your conclusion in (d)