Question

11. (1 point) Which of the following sets are countable? A. {0,1}" B. {LL C{0,1}} C. The set of all numbers {al a € Z or a = be where b, c € Z}, where Z is the set of all integers. D. Both A and C. E. All of A,B and C. 12. (1 point) How do we know that some languages may not be Turing-recognizable? A. Atm is an example of a language which is not Turing-recognizable. B. The number of possible languages over an alphabet = {0,1} is larger than the set of all Turing machines. C. The language HALTTM = {(M,w)| M halts on w} is not recognizable. D. ATM is not recognizable. E. Follows by either B or D.

Answer 1

Solution 11:-

Correct option - B

Option A is not valid as it includes all the strings of 0 and 1 and kleen clousre makes it all possible combinations which is uncountable. Option C is invalid as b , c belongs to set of intergers and there can be many intergers which follows a=b+c/2. Since option A,C is invalid so option D , E are invalid. Subset of {0,1}* can be countable so option B is valid.

Solution 12:-

Correct option - E

Option A is invalid as it is turning recognizable. Option C is invalid as for the stated language it is turning recognizable.
Option B , D are correct as the stated in option D is an example of Turing unrecognizable and number of all possible Language is included in the power set and for Turing unrecognizable the power set of the language is greater than set of Turing machine.