(30 points) We can use Rice's theorem to show that a language is undecidable. For example: Consider the language INFINITETM = {?M) | M is a TM and L(M) is an infinite language). It satisfies the two conditions of Rice's theorem. First, it is nontrivial because some TMs have infinite languages and others do not. Second, it depends only on the language. If two TMs recognize the same language, either both have descriptions in INFINITETM or neither do. Consequently, Rice's theorem implies that INFINITETM s undecidable. Use Rice's theorem to prove the undecidability of the following languages: (a) {(A) I M is a TM and 1011 ? c(M)) (b) ALLTM = {(M? 1 M is a TM and L(M) = ?*) (30 points) We can use Rice's theorem to show that a language is undecidable. For example: Consider the language INFINITETM = {?M) | M is a TM and L(M) is an infinite language). It satisfies the two conditions of Rice's theorem. First, it is nontrivial because some TMs have infinite languages and others do not. Second, it depends only on the language. If two TMs recognize the same language, either both have descriptions in INFINITETM or neither do. Consequently, Rice's theorem implies that INFINITETM s undecidable. Use Rice's theorem to prove the undecidability of the following languages: (a) {(A) I M is a TM and 1011 ? c(M)) (b) ALLTM = {(M? 1 M is a TM and L(M) = ?*)