CS 350 Assignment 3: Computability and Complexity 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Computer Science 350 (2022)
Assignment 3: Computability and Complexity
Questions
1. Question 1
(a) Define the notion of Turing-recognisable (computably enumerable) language
over the alphabet {a, b}.
(b) Construct the largest Turing-recognisable language, if it exists. Justify your answer.
(c) Construct the smallest infinite Turing-recognisable language, if it exists. Justify your answer.
2. For each N > 0 consider the language XN = {〈M〉| M has more than N states}.
a) Does there exist N such that XN satisfies all hypotheses of Rice’s Theorem? Justify your answer.
b) Does there exist N such that XN is undecidable? Justify your answer.
c) Can you obtain your answer to b) using Rice’s Theorem? Justify your answer.
3. Let X = {2n + 1 | n ≥ 0} and Y = {n11 | n ≥ 0}.
a) Let g(x) = x11 . Is X m-reducible to Y via g?
b) Construct a computable function f 
g such that X is m-reducible to Y via the function f and prove that it has the required property.
2022-06-01