Decidability

Decidability theory draws the line between problems that can be solved algorithmically and those that cannot. Understanding these limits is essential for knowing when to seek alternative approaches.

Language Classes

Decidable (Recursive) Languages

A language L is decidable if there exists a TM that:

Accepts every w ∈ L
Rejects every w ∉ L
Always halts (never loops)

The TM is called a decider.

Recognizable (Recursively Enumerable) Languages

A language L is recognizable (RE) if there exists a TM that:

Accepts every w ∈ L
For w ∉ L: rejects or loops (may never halt)

The TM is called a recognizer.

Co-Recognizable Languages

L is co-recognizable if L̄ (complement) is recognizable.

Relationships

Decidable = Recognizable ∩ Co-Recognizable

Theorem: L is decidable iff both L and L̄ are recognizable.

Proof: If L and L̄ are recognizable, run both recognizers in parallel (interleaving steps). One must accept (since every string is in L or L̄). If L's recognizer accepts first → accept. If L̄'s accepts first → reject. This always halts. ∎

Hierarchy:
All languages (uncountable — most are not even recognizable!)
  ⊃ Recognizable (RE)
    ⊃ Decidable (Recursive)
      ⊃ Context-Sensitive
        ⊃ Context-Free
          ⊃ Regular

The Halting Problem

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

HALT = {⟨M, w⟩ | M halts on input w}

Theorem (Turing, 1936): HALT is undecidable.

Proof (by contradiction)

Assume a decider H exists for HALT:

H(⟨M, w⟩) = { accept  if M halts on w
             { reject  if M loops on w

Construct a new TM D:

D(⟨M⟩):
    Run H(⟨M, ⟨M⟩⟩)
    If H accepts: loop forever
    If H rejects: accept

What happens when we run D(⟨D⟩)?

If D halts on ⟨D⟩: H accepts → D loops. Contradiction.
If D loops on ⟨D⟩: H rejects → D accepts (halts). Contradiction.

Either way, we have a contradiction. So H cannot exist. ∎

Note: HALT is recognizable (just simulate M on w — if M halts, accept). But it's not co-recognizable (complement is not recognizable).

Reduction Techniques

Mapping Reduction

A mapping reduction from L₁ to L₂ (written L₁ ≤_m L₂) is a computable function f: Σ* → Σ* such that:

w ∈ L₁ iff f(w) ∈ L₂

Meaning: If we can solve L₂, we can solve L₁ (by applying f first). Equivalently: if L₁ is undecidable, then L₂ is undecidable.

Using Reductions

To prove a problem P is undecidable:

Pick a known undecidable problem Q (usually HALT or A_TM).
Show Q ≤_m P (construct a reduction from Q to P).
Since Q is undecidable and Q ≤_m P, P must be undecidable.

Turing Reduction

A Turing reduction L₁ ≤_T L₂ means: L₁ is decidable given an oracle for L₂. More powerful than mapping reduction.

Undecidable Problems

A_TM (Acceptance Problem)

A_TM = {⟨M, w⟩ | M is a TM that accepts w}

Undecidable (same proof as halting problem, essentially).

E_TM (Emptiness Problem)

E_TM = {⟨M⟩ | L(M) = ∅}

Undecidable. Proof: Reduce A_TM to Ē_TM. Given ⟨M, w⟩, construct M' that ignores its input, simulates M on w, and accepts its input if M accepts w. Then L(M') = ∅ iff M doesn't accept w.

EQ_TM (Equivalence Problem)

EQ_TM = {⟨M₁, M₂⟩ | L(M₁) = L(M₂)}

Undecidable. Not even recognizable (nor co-recognizable).

Rice's Theorem

Theorem (Rice, 1953): Every non-trivial property of the language of a TM is undecidable.

Formally: Let P be a property of RE languages (a set of RE languages). If P is non-trivial (some TMs have property P and some don't), then:

L_P = {⟨M⟩ | L(M) ∈ P}

is undecidable.

Examples of undecidable properties (by Rice's theorem):

"Does M accept the empty string?"
"Is L(M) finite?"
"Is L(M) regular?"
"Is L(M) = Σ*?"
"Does L(M) contain at least one string?"

Note: Rice's theorem applies to properties of the language L(M), not to properties of the machine M itself. "Does M have fewer than 100 states?" IS decidable (it's about the machine's description, not its language).

Post Correspondence Problem

PCP: Given pairs of strings (t₁/b₁), (t₂/b₂), ..., (tₙ/bₙ), is there a sequence of indices i₁, i₂, ..., iₖ such that:

t_{i₁} t_{i₂} ... t_{iₖ} = b_{i₁} b_{i₂} ... b_{iₖ}

The concatenation of the top strings equals the concatenation of the bottom strings.

Example: (a/ab), (b/a), (ab/b). Solution: 1, 2, 1, 3 → top: a·b·a·ab = abaab, bottom: ab·a·ab·b = abaab. ✓

Theorem: PCP is undecidable.

PCP is useful for proving undecidability of problems about grammars and string rewriting systems (simpler to reduce from PCP than from TMs directly).

Undecidable Problems About CFGs

Using PCP reductions:

| Problem | Decidable? | |---|---| | Is L(G) = ∅? | Decidable | | Is L(G) = Σ*? | Undecidable | | Is G ambiguous? | Undecidable | | Is L(G₁) = L(G₂)? | Undecidable | | Is L(G₁) ⊆ L(G₂)? | Undecidable | | Is L(G₁) ∩ L(G₂) = ∅? | Undecidable | | Is L(G) regular? | Undecidable | | Is L(G) inherently ambiguous? | Undecidable |

Contrast: All of these are decidable for regular languages!

Decidable Problems Summary

| Problem | Regular | CFL | Recursive | RE | |---|---|---|---|---| | Membership | Decidable | Decidable | Decidable | Recognizable only | | Emptiness | Decidable | Decidable | Undecidable | Undecidable | | Finiteness | Decidable | Decidable | Undecidable | Undecidable | | Equivalence | Decidable | Undecidable | Undecidable | Undecidable | | Universality | Decidable | Undecidable | Undecidable | Undecidable |

Implications for CS

What We Can't Automate

Perfect bug detection: "Does this program have a bug?" is undecidable (Rice's theorem — any non-trivial semantic property).
Perfect optimization: "Is this the fastest possible program for this task?" is undecidable.
Perfect type checking: For sufficiently expressive type systems, type checking may be undecidable (e.g., C++ template metaprogramming).
Perfect malware detection: "Does this program contain malicious behavior?" is undecidable.

What We Can Do

Approximation: Sound (no false negatives) or complete (no false positives) analysis, but not both.
Restriction: Restrict the language/problem to a decidable subset (e.g., regular expressions instead of arbitrary grammars).
Heuristics: Techniques that work well in practice even if they can't solve all cases (SAT solvers, type inference, static analysis).
Semi-decision: Recognize "yes" instances (even if we can't recognize "no" instances). Useful for verification and testing.

Applications in CS

Software verification: Rice's theorem tells us perfect automated verification is impossible in general. We use sound approximations (abstract interpretation, type systems, model checking on restricted models).
Compiler design: Undecidability of CFG equivalence means we can't always optimize grammars optimally. Practical parsers use decidable subsets (LR, LL).
Security: Perfect malware detection is undecidable. Use heuristics, signatures, behavior analysis.
AI safety: Undecidability limits what we can formally guarantee about AI systems.
Formal methods: Knowing the boundaries of decidability guides tool design — focus on decidable fragments.