Computer Science 350 (2020)
Assignment 3: Computability and Complexity
This assignment is worth 100 marks representing 5% of your total course grade. Due date: 7 June 2020 submitted via Canvas before 23.55
Notes
• To obtain full credit, your script must clearly explain why your answers are correct.
• You can use without proof any result proved in class. You need to state correctly the result and show how it applies
to the specific problem you solve.
• Your submissions are expected to adhere to the Academic Integrity standards. You cannot submit any mate- rial for assessment that isn’t your own work.
Questions
1. LetX ={2n+1|n≥0}andY ={n10 |n≥0}.
a) Let g(n) = n10. Is X m-reducible to Y via g?
b) Construct a computable function f such that X is m-reducible to Y via the function f and prove that it has the required property.
c) Construct infinitely many computable functions Fi such that X is m-reducible to Y via the function Fi and prove that they have the required property.
2. For each N > 0 consider the language RN = {⟨M ⟩ | M is a Turing machine with more than N states}.
a) Does there exist N such that RN satisfies all hypotheses of Rice’s Theorem? Justify your answer.
b) Does there exist N such that RN is undecidable? Justify your answer.
c) Can you obtain your answer to b) using Rice’s Theorem? Justify your answer.
d) Does the language L = {⟨M ⟩ | L(M ) is regular} satisfy all hypotheses of Rice’s Theorem? Justify your answer.
3. Consider the language:
L = {⟨M, x⟩ | M is a Turing machine and M rejects x}. a) What does it mean that “M rejects x”?
b) Is the following
Theorem. The language L is undecidable.
correct? Respond with yes or no.
c) Consider the following proof for the Theorem:
We have L = A ̄TM (X ̄ is the complement of X) and we know that ATM is undecidable, so L is also undecidable.
Is the proof correct? In the affirmative justify its correctness; in the negative give either a correct proof or a proof that L is decidable.
d) Prove that L is Turing recognisable.
4. Let f be a strictly increasing computable function mapping positive integers into positive integers. Prove that the set {f (x) | x ∈ N} is decidable.
5. a) Prove that for every computable function f from {0, 1}∗ to {0, 1}∗ , there exists a constant c such that for all x we have K(f(x)) ≤ K(x) + c.
b) Define a bijective computable function from {0, 1}∗ to {0, 1}∗ .
c) Give an example of a bijective computable function from {0, 1}∗ to {0, 1}∗ and prove that is has the required properties.
d) Prove that the inverse of a computable bijection f from {0, 1}∗ to {0, 1}∗ is also computable.
e) Prove that for every bijective computable function f from {0, 1}∗ to {0, 1}∗ , there exists a constant c such that for all x we have K(x) ≤ K(f(x)) + c.