Reductions and proving undecidability

1. Is HALT_TM decidable? RE?
   Stuck? Peek at 5.2 The diagonal language and the halting problem

   • L_d = {wᵢ : wᵢ ∉ L(Mᵢ)}: not RE (co-RE).
   • A_TM = {⟨M,w⟩ : M accepts w}: RE, not recursive; complement not RE.
   • HALT_TM: RE, undecidable; complement not RE.
   • REC = RE ∩ co-RE.

   Read lesson 5.2

2. Which closure property fails for RE?
   Stuck? Peek at 4.3.3 Closure of REC and RE; L and L̅ both RE ⇒ L recursive

   • REC closed: ∪ ∩ complement − concat * reversal h⁻¹; not h.
   • RE closed: ∪ ∩ concat * reversal h h⁻¹; not complement, not difference.
   • L, L̅ ∈ RE ⇒ L ∈ REC. L ∈ RE − REC ⇒ L̅ ∉ RE.

   Read lesson 4.3.3

3. What is the contrapositive of P ⇒ Q?
   Stuck? Peek at 0.2.3 Proof techniques

   • P ⇒ Q false only when P true, Q false. Contrapositive ¬Q ⇒ ¬P ≡ original. Converse/inverse are NOT.
   • Contradiction: assume ¬S, derive the impossible. Used for “no machine can…” proofs.
   • Induction: base S(n₀) + step S(k) ⇒ S(k+1). Strong induction assumes all S(≤k).
   • One counterexample kills a “for all”. Examples never prove it.

   Read lesson 0.2.3

To show a new problem is unsolvable, you don’t redo the diagonal argument. You show that a solver for the new problem would solve an old unsolvable one. That transfer is a reduction. The single most common GATE error in this topic is reducing in the wrong direction — this lesson drills the direction until it is automatic.

You can convert any instance of problem A into an instance of problem B with the same answer. If B is easy, what about A? If A is impossible, what about B?

Prediction check

If B is easy, A is easy (convert, then solve B). If A is impossible, B is impossible (otherwise A would be easy). Hardness flows from A to B, along the arrow A ≤ B.

Mapping reductions

• B decidable ⇒ A decidable. Equivalently, A undecidable ⇒ B undecidable.
• B RE ⇒ A RE. Equivalently, A not RE ⇒ B not RE.
• A ≤ B ⇔ A̅ ≤ B̅ (same f).
• ≤ is transitive.

The direction trap

To prove your problem P is undecidable, reduce a known undecidable problem to P: A_TM ≤ P. Reducing P to A_TM only shows P is no harder than A_TM — useless for hardness.

Worked reductions

• A_TM ≤ HALT_TM: f(⟨M, w⟩) = ⟨M′, w⟩ where M′ runs M on w, and loops forever if M rejects. M′ halts ⇔ M accepts.
• A_TM ≤ complement of E_TM (E_TM = {⟨M⟩ : L(M) = ∅}): f(⟨M, w⟩) = ⟨M_w⟩ where M_w ignores its input x and runs M on w. L(M_w) = Σ* if M accepts w, else ∅. So E_TM is undecidable; its complement is RE, so E_TM is not RE.
• EQ_TM = {⟨M₁, M₂⟩ : L(M₁) = L(M₂)}: E_TM reduces to it (compare with a machine accepting nothing), and its complement is also not RE — EQ_TM is neither RE nor co-RE.

A standard results table

Every row below follows from A_TM by a reduction (or from Rice, next lesson).

Putting it together

• A ≤ B transfers decidability backwards and hardness forwards.
• Always reduce from a known hard problem to the new one.
• Standard results: E_TM co-RE, NE_TM RE, EQ_TM and TOTAL neither.

A ≤ B   :   "B is at least as hard as A"
            hardness travels →   (A undecidable ⇒ B undecidable)
            easiness travels ←   (B decidable  ⇒ A decidable)
to prove P hard:   A_TM ≤ P   (never P ≤ A_TM)

Proving each property undecidable one reduction at a time is tedious. Rice’s theorem does them all at once: every non-trivial question about the language of a TM is undecidable.

1. MCQ

   To prove P undecidable, you show:

   1. P ≤ A_TM
   2. A_TM ≤ P
   3. P ≤ a regular language
   4. P is RE
2. MSQ

   A ≤ₘ B. Which follow?

   1. B decidable ⇒ A decidable
   2. A undecidable ⇒ B undecidable
   3. B RE ⇒ A RE
   4. A decidable ⇒ B decidable
3. MCQ

   E_TM = {⟨M⟩ : L(M) = ∅} is:

   1. decidable
   2. RE but not decidable
   3. co-RE but not RE
   4. neither RE nor co-RE
4. MCQ

   EQ_TM is:

   1. decidable
   2. RE
   3. co-RE
   4. neither RE nor co-RE

• mapping reduction A ≤ₘ B
• computable function
• direction of a reduction
• E_TM, NE_TM, EQ_TM, TOTAL_TM

1. To prove P undecidable, which reduction?
   Reveal answer

   A_TM ≤ P (known hard → new).
2. A ≤ B and B decidable ⇒ ?
   Reveal answer

   A decidable.
3. Is E_TM RE?
   Reveal answer

   No (it is co-RE).
4. Is EQ_TM RE or co-RE?
   Reveal answer

   Neither.