Pls answer all part of the question correctly and show all work.

Question 1:

a)Consider the following faulty proof that any language L is decidable, which has multiple fatal errors. Identify two of these errors by the lines in which they appear, and explain what is wrong with them. (For a few extra points, identify and explain more than two errors.)

i. Because is countable, so is L.

ii. Therefore, there exists an ordered (finite or infinite) list of Ls elements, as L = {x1, x2, x3, . . .}. iii. We use this to define a Turing machine D, defined as: D(x): A. Check whether x = x1, x = x2, x = x3, and so on. B. If any of these checks hold, then accept; otherwise, reject. iv. It is clear by inspection that D decides L, because D accepts every string x L and rejects every string x L. v. Therefore, L is decidable.

(b) Prove that any infinite language L (even a decidable one) contains an undecidable subset. For example, the (trivially decidable) language contains an undecidable language (i.e., subset). Hint: Can you view a subset of L as an infinite binary sequence?

(c) Let L1, L2, L3, . . . be countably many languages over possibly different alphabets, i.e., Li i where each i is some finite alphabet that may vary with i. Prove that L = L1 L2 L3 is countable. This should hold even if the combined alphabet = 1 2 3 is infinite. For example, we might have 1 = {0, 1}, 2 = {0, 1, 2}, and i = {0, 1, 2, . . . , i} in general. Then the combined alphabet = {0, 1, 2, . . .} = N is the infinite set of natural numbers, so L is a set of strings whose characters may be any natural numbers.