# 图灵机代写 | 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.