CS 332: Theory of Computation Prof. Boston University November 11, 2021
Homework 8 – Due Tuesday, November 16 2021 at 11:59 PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without as- sistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators and write “Collaborators: none” if you worked by yourself. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Note You may use various generalizations of the Turing machine model we have seen in class, such as TMs with two-way infinite tapes, stay-put, or multiple tapes. If you choose to use such a generalization, state clearly and precisely what model you are using.
Copyright By PowCoder代写 加微信 powcoder
Problems There are 4 required problems and 1 bonus problem.
1. (Complementary TMs) Consider the following computational problem: Given TMs M1 and M2, is it the case that L(M1) = L(M2)? This problem is captured by the language CTM = {⟨M1, M2⟩ | M1, M2 are TMs and L(M1) = L(M2)}.
(a) If f is a mapping reduction from ATM to CTM, what should the inputs and outputs to f be? (As in Lecture 17, slide 17.)
(b) Describe a TM computing a mapping reduction from ATM to CTM and explain why this TM is correct.
(c) Explain why part (b) implies that CTM is not Turing-recognizable.
(d) Use a (different) mapping reduction to prove that CTM itself is not Turing-recognizable.
2. (Mapping Reductions) Prove the following general statements about existence of mapping re- ductions.
(a) Let A be an arbitrary recognizable language, and suppose A ≤m A. Show that A is decidable. (Hint: Recall that a language is decidable iff both it and and its complement are recognizable.)
(b) Let A be an arbitrary decidable language and let B be an arbitrary language other than ∅ or Σ∗. (That is, there exist strings w1 ∈ B and w0 ∈/ B.) Show that A ≤m B.
3. (Review of asymptotic notation) Use the formal definitions of O and o notation to prove the following statements. You may also use the fact that f(n) = o(g(n)) if limn→∞ f(n)/g(n) = 0, as well as assume basic math facts like n ≤ n2 for all n ≥ 1 without proof.
(a) Prove that 2n + n log n = O(n log2 n). (The notation log2 n means (log n)2.) √
(b) Prove that 4 n = 2o(n).
4. (Asymptotic notation examples) This problem will be graded automatically by Gradescope. Please enter your answers manually by completing the assignment Homework 8-Problem 4. For each of the following, select true or false using the radio buttons on Gradescope. All logarithms are base 2 unless otherwise stated.
(a) 3n = 2O(n) (b) 22n =O(22n)
(c) nn = O(n!) (d) n = o(n)
(e) 2n = o(n2) (f) 2332 = O(n) (g) 16n = O(n)
(h) n4 = O(n2 logn)
(i) nlogn+10n=O(n2) (j) 3n = O(2n)
(k) 2n = o(3n) (l) 1 = o(n)
(m) 2logn = o(logn) (n) 31 = o(1)
5. (Bonus problem) Show that the assumption that A is recognizable in Problem 2 is necessary: Give an example of an unrecognizable language A such that A ≤m A.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com