0017 Computational Complexity problem sheet 4.
1. Show that the mapping-reducibility relation ≤ is reflexive and transitive, thatis,forallLwehaveL≤L,andifL≤L′ ≤L′′,thenalsoL≤L′′.
Solution: For reflexivity take the identity function as computable f. For transitivity, if f witnesses L ≤ L′ and g witnesses L′ ≤ L′′, then their composite g ◦ f witnesses L ≤ L′′. Observe that computability of g ◦ f follows from computability of f and of g.
2. Prove that, if L′ ≤ L and L is recognisable, then L′ is also recognisable.
Copyright By PowCoder代写 加微信 powcoder
Solution: Since L′ ≤ L, we have a computable f such that x ∈ L′ iff f(x) ∈ L. Call Mf the TM computing f. By assumption L is recognisable, so call ML the TM recognising it. Now, the TM recognising L′ works as follows: on input x, run Mf on x, which produces f(x) on tape, then run ML on f(x). If ML accepts, accept, otherwise loop.
3. Prove that HALT ≤ EQ, i.e., the language of the halting problem is mapping-reducible to the language of equivalence of Turing machines. The two languages are defined as on the slides of Lecture 10–11.
Solution: The proof structure is the same as the proof that HALT ≤ EQ− given in the slides of Lecture 10–11.
First, if y ̸= code(M) for any M, then let f(⟨y,x⟩) be ⟨y,y⟩, so that f(⟨y,x⟩) ∈/ EQ. Second, if y = code(M) for some M, then let f(⟨y,x⟩) = ⟨code(M1),code(M2)⟩, where
• M1 istheTMthatrunsM onxandoutputs1iffM halts. • M2 is the TM that outputs 1 on any input.
One can check that such f witnesses HALT ≤ EQ.
4. Given an alphabet Σ, suppose an encoding code(−) of Turing machines
as strings over Σ. Consider the language
EL={x∈Σ⋆ |x=code(M)forsomeT.M.M andLM =∅}.
That means, M loops on any input string.
(a) Prove that EL−, the complement of EL, is recognisable.
(b) Prove that HALT is not mapping-reducible to EL (hint: use what you know about reducibility and complements.)
Solution: Check the solution of exercise 5.5 in Sipser’s textbook “Introduction to the theory of computation”.
5. What of the following are language properties? Which are trivial? Justify your answers.
(a) {y | y = code(M) and LM = L− for some finite language L} (b) {y | y = code(M) and M halts on some input}
(c) {y | y = code(M) and M never returns to its initial state } (d) {y|y=code(M)andε∈LM}
(e) {y | y = code(M) and LM is recognisable} Solution:
(a) It is a non-trivial language property
(b) It is a non-trivial language property.
(c) It is non-trivial, but it is not a language property: we can adjust a TM such that it never (or always) returns to its initial state, while accepting the same language.
(d) It is a non-trivial language property.
(e) It is a trivial language property (LM is recognisable by definition).
We now recall some basics of set theory that will be used in the next lecture. A set X is be countably infinite if there is a bijective function f : N → X.
6. Prove that the set Ne of even natural numbers is countably infinite. Solution: For example, f : N → Ne given by f(n) = 2n. It’s easy to
see this function is injective and surjective, and thus bijective.
7. The set of integers, Z, is defined as containing all the natural numbers along with their negative counterparts (and 0). Formally Z = N ∪ −N ∪ {0}, where −N = {−1, −2, −3, . . . }. Prove that Z is countably infinite.
Solution: For example the function f : N → Z defined by f(n) = n2 if n is even, f(n) = −(n−1) if n is odd. It’s easy to see this function is
injective and surjective, and thus bijective.
8. Let the alphabet Σ be countably infinite. Prove that Σ⋆ is countably infinite. You can be slightly informal, in the sense that we do not expect a formal definition of the bijection Σ⋆ → N.
Solution: We give a means of listing all the elements of Σ∗. First suppose that the characters in the alphabet are listed a1, a2, . . . . We define the index of a string to be the sum of the indices of its characters, so, for example, the string a4a7a1a22 would have index 4+7+1+22 = 34. We now define for each natural number n the set Sn = the set of all strings in Σ∗ with index n. Then each Sn is finite (S0 contains only the empty string) and so can be ordered. We list the elements of Σ∗ by listing the elements of each Sn in turn.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com