3. Question 3–Turing Decidability and Turing Recognizability–True or False? For each of the following statements: determine (and state clearly) whether it is true or false, and give a brief argument (proof) of your claim: (a) Every TM M halts computation on input ?. (b) We can decide if there exists a word w that a given TM M accepts by verifying if there is a directed path from the start state q0 to accept state qaccept in a state diagram of M. (c) If languages L1 and L2 over ? are both Turing-decidable with L1 ? L2, then every language L that is sandwiched between them, that is L1 ? L ? L2 also is Turing-decidable. (d) If languages L1 and L2 over ? are both Turing-recognizable, then their intersection L1 ?L2 is also Turing-recognizable. (e) For every language L over ? that is Turing-recognizable, at least one of L and LC is Turing-decidable.