Decidability Undecidability Notes & Formulas

1. Definition

• Decidable (Recursive) language: A TM exists that always halts and correctly accepts/rejects every input
• Semi-decidable (Recursively Enumerable): A TM exists that accepts all strings in the language but may loop forever on strings NOT in the language
• Undecidable: No TM exists that decides the language

2. Decidability Hierarchy

Decidable ⊂ Semi-decidable (RE) ⊂ All Languages

• If L is decidable → L is RE, complement L̄ is also decidable and RE
• If L is RE but not decidable → L̄ is NOT RE
• If L is not RE → L̄ may or may not be RE

3. Halting Problem (Very Important)

HP: Given TM M and input w, does M halt on w?

• HP is Semi-decidable (RE) - TM accepts if M halts on w, loops forever if M doesn't halt
• HP is Undecidable - no TM can always answer YES/NO

Proof sketch (Diagonalization):
Assume TM H decides HP. Build TM D: on input M, run H(M,M):

• If H says "halts" → D loops forever
• If H says "loops" → D halts
  Running D on D gives contradiction → H cannot exist.

4. Important Decidable Problems

For Regular Languages (all decidable):

• Membership: is w ∈ L(DFA)?
• Emptiness: is L(DFA) = ∅?
• Finiteness: is L(DFA) finite?
• Equivalence: is L(DFA₁) = L(DFA₂)?

For CFLs (partially decidable):

• Membership: is w ∈ L(CFG)? (CYK algorithm, O(n³))
• Emptiness: is L(CFG) = ∅?
• Finiteness: is L(CFG) finite?
• Undecidable: Equivalence, Ambiguity, L(CFG) = Σ*, intersection non-empty

5. Important Undecidable Problems (Very Important)

| Problem | Status |
|---|---|
| Halting Problem | RE, Undecidable |
| Emptiness of TM: L(TM) = ∅? | Co-RE, Undecidable |
| Membership for TM | RE, Undecidable |
| Equivalence of two TMs | Undecidable, not RE |
| Post Correspondence Problem (PCP) | Undecidable |
| CFG ambiguity | Undecidable |
| CFG equivalence | Undecidable |
| L(CFG) = Σ* | Undecidable |
| Intersection of two CFGs non-empty | Undecidable |

6. Rice's Theorem (Very Important)

Any non-trivial property of the language recognized by a TM is undecidable.

• Trivial property: Either all TMs have it or no TM has it
• Non-trivial: Some TMs have it, some don't
• Examples of undecidable (by Rice's): "Does TM accept ε?", "Is L(TM) regular?", "Is L(TM) finite?", "Is L(TM) = ∅?"

7. Reductions

If A reduces to B (A ≤ B):

• If B is decidable → A is decidable
• If A is undecidable → B is undecidable
• Reduction preserves undecidability upward

8. GATE Trick

Rice's theorem is the fastest way to prove undecidability - check if property is about the language (not the TM machine itself) and is non-trivial. Halting problem is the standard reduction target. If L is undecidable RE, then L̄ is not RE - this is directly tested. "Does TM halt on empty input?" - undecidable by Rice's theorem.