COMS 331: Theory of Computing, Spring 2021 Homework Assignment 8
Due at 10:00PM, Wednesday, March 31, on Gradescope.
Recall that we have used the string-pairing function
⟨·,·⟩:{0,1}∗ ×{0,1}∗ −→{0,1}∗
defined by
for all x,y ∈ {0,1}∗.
⟨x, y⟩ = 0|x|1xy
Given a language B ⊆ {0, 1}∗, define the language ∃B ⊆ {0, 1}∗ by
∃B = {x ∈ {0,1}∗ |(∃w ∈ {0,1}∗)⟨x,w⟩ ∈ B}.
Problems 50 and 51 characterize computable enumerability in terms of unbounded existential search.
Problem 50. Let B ⊆ {0, 1}∗. Prove: If B is c.e., then ∃B is c.e.
Problem 51. Prove: For every c.e. language A ⊆ {0, 1}∗, there is a decidable language B ⊆ {0, 1}∗
such that A = ∃B.
Recall that the join of two languages A, B ⊆ {0, 1}∗ is
A ⊔ B = {x0 | x ∈ A} ∪ {y1 | y ∈ B}.
Problem 52. Let A, B, C ⊆ {0, 1}∗. Prove: If A ≤m C and B ≤m C, then A ⊔ B ≤m C.
1
Problem 53. Let A ⊆ {0,1}∗, and let Ac = {0,1}∗ − A be the complement of A. Prove: If A is ≤m-complete for CE, then A ⊔ Ac is neither c.e. nor co-c.e.
Problem 54. Prove that {k ∈ N|Mk(3) ↑} is ≤m-complete for coCE.
Problem 55. Prove that {k ∈ N|(∀l ∈ N)Mk(l) ↓} is ≤m-hard for CE.
Problem 56. Let f : N −→ N be computable. Prove: If f(n) < f(n+1) for all n ∈ N, then {f (n) | n ∈ N} is decidable.
2