Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
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.