图灵机代写 | Computer Science 350 (2020) Assignment 3: Computability and Complexity

这个作业是回答图灵机相关的问题
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 material for assessment that isn’t your own work.
Questions
1. Let X = {2n + 1 | n ≥ 0} and Y = {n
10 | n ≥ 0}.
a) Let g(n) = n
10. 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 = {hMi | 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 = {hMi | L(M) is regular} satisfy all hypotheses of Rice’s Theorem? Justify your answer.
3. Consider the language:
L = {hM, xi | 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.