I. Let be a finite alphabet and let T be the set of all Turing machines over this alphabet. (i) Show that T is countable. That is, find an injective function f : T N. (i) Let 1-( (T, i) | T is a Turing machine and iE is input for it } Show that I is countable. (iii) Show that * is countable. iv) Recll that the power set of a set S is Show that P() is countable. v) Fill in the logic to this argument proving the existence of non-computable problems. Let L be the set of languages accepted by some machine from T. From the above problems, we can conclude that L is countable, that L c P(y), and that P(S') is uncountable (be sure to explain how these follow frorn above). This implies that P(*) \L is not empty, so there is some S E P(S') \ L. There is no Turing machine over which accepts this language, so it is not computable. I. Let be a finite alphabet and let T be the set of all Turing machines over this alphabet. (i) Show that T is countable. That is, find an injective function f : T N. (i) Let 1-( (T, i) | T is a Turing machine and iE is input for it } Show that I is countable. (iii) Show that * is countable. iv) Recll that the power set of a set S is Show that P() is countable. v) Fill in the logic to this argument proving the existence of non-computable problems. Let L be the set of languages accepted by some machine from T. From the above problems, we can conclude that L is countable, that L c P(y), and that P(S') is uncountable (be sure to explain how these follow frorn above). This implies that P(*) \L is not empty, so there is some S E P(S') \ L. There is no Turing machine over which accepts this language, so it is not computable