TC

  • Homework 3
  • many-one reduccions
  • some quizzes (to do at home for next class)

April 28, 2026

Exercises from Homework 3

  • Exercise 3.20
  • Exercise 3.6 (parts a, b)

Many-one reductions

Definition 1 Let A\subseteq \Sigma^*, B\subseteq \Gamma^*, A many-one reduces to B (A\leq_m B) if there exists a total computable function f: \mathbb \Sigma^* \to \mathbb \Gamma^* s.t.

  • if x\in A, then f(x)\in B
  • if x\notin A, then f(x)\notin B

Example 1 \mathtt{K}=\{x\mid M_x(x)\!\downarrow\} \leq_m \{(x,y) \mid M_x(y)\!\downarrow\}

f(x)=?

  • \leq_m is a good notation
    • A\leq_m A
    • A\leq_m B and B\leq_m C implies A\leq_m C
  • If A\leq_m B and A is hard then B is also hard
    • if A\leq_m B and A\notin \mathbf{R}, then B\notin \mathbf{R}
    • if A\leq_m B and A\notin \mathbf{RE}, then B\notin \mathbf{RE}
    • if A\leq_m B and A\notin \mathbf{coRE}, then B\notin \mathbf{coRE}

\mathtt{K}\leq_m \cdots \leq_m \{(G_1,G_2) \mid G_1,G_2 \text{ are CFGs with } \mathscr{L}(G_1)\cap \mathscr{L}(G_2)\neq \emptyset\}

\overline{\mathtt{K}}\leq_m \cdots \leq_m \{G \mid G \text{ is a CFG with } \mathscr{L}(G)=\{a,b\}^*\}

We can classify languages L as

  • L\in \mathbf{R} (decidable)
  • L\in \mathbf{RE}\setminus \mathbf{R} (semi-decidable but not decidable)
  • L\in \mathbf{coRE}\setminus \mathbf{R} (not semi-decidable but the complement is semi-decidable)
  • L\notin \mathbf{RE}\cup \mathbf{coRE} (neither L nor its complement are semi-decidable)

How?

  • Construct TMs to prove L\in \mathbf{R} (or \mathbf{RE} or \mathbf{coRE})
  • Use many-one reductions to show L\notin \mathbf{RE} or L\notin \mathbf{coRE}
    Often by using \mathtt{K}\leq_m L or \overline{\mathtt{K}}\leq_m L

Exercises from Homework 3

  • Closure properties of \mathbf{R}, \mathbf{RE}, \mathbf{coRE}
    • Exercise 3.3 (parts 1a, 1b)
    • Exercise 3.3 (parts 2a, 2b)
    • Exercise 3.4 (parts 2a, 2b)
    • Exercise 3.4 (parts 3a, 3b)
  • Exercise 3.5 (parts 1a)
  • Exercise 3.9 (parts a, b)

Quiz

Given languages A,B,C s.t. A\in \mathbf{RE}\setminus \mathbf{R} and A=\overline{B\cup C}. Which of the following options for B and C are possible?

(a) B\in \mathbf{RE} and C\in \mathbf{RE}
(b) B\in \mathbf{coRE} and C\in \mathbf{coRE}
(c) B\in \mathbf{RE} or C\in \mathbf{RE}
(d) B\in \mathbf{coRE} or C\in \mathbf{coRE}

Quiz

Let L=\{n\in \mathbb N \mid \exists p\geq n\ p\text{ and } p+2 \text{ are both prime numbers}\}.

Which of the following do you know for sure it is true?

(a) L\notin \mathbf{RE}\cup \mathbf{coRE}
(b) L\in \mathbf{RE}
(c) L\in \mathbf{coRE}
(d) L\in \mathbf{R}

Quiz

Which of the following sentences on languages A,B\subseteq \{0,1\}^* is false?

(a) If A\notin \mathbf{R}, then A\cup\{0101\}\notin \mathbf{R}.
(b) If A\notin\mathbf{R} and B is finite, then A\cup B\notin \mathbf{R}.
(c) If A\in \mathbf{RE}, there are infinitely many Turing machines that recognize A.
(d) If A=\mathscr{L}(M) where M is a Turing machine that does not halt on 010, then A\in \mathbf{RE}\setminus \mathbf{R}.