Decidability and Recognizability

Decidability and Recognizability

A problem is decidable if there exists a Turing machine that always halts and gives the correct yes/no answer for every input. A problem is recognizable (or semi-decidable) if there exists a TM that halts and says "yes" for positive instances, but may loop forever on negative instances.

Decidable is strictly stronger than recognizable. Every decidable problem is recognizable, but not every recognizable problem is decidable.

Formal Definitions

Decidable (Recursive):
  A language L is decidable if there exists a TM M such that:
  - M halts on ALL inputs
  - M accepts w iff w ∈ L
  - M rejects w iff w ∉ L

Recognizable (Recursively Enumerable):
  A language L is recognizable if there exists a TM M such that:
  - M accepts w iff w ∈ L
  - M may loop forever if w ∉ L (or may reject)

Relationship:
  Decidable ⊂ Recognizable

  All decidable languages are recognizable.
  Some recognizable languages are NOT decidable.

Examples

Decidable languages:
  - {w | w is a valid binary number}
  - {w | w has equal 0s and 1s}
  - {G, w | CFG G generates string w}
  - {A | DFA A accepts string w}

Recognizable but NOT decidable:
  - {w | TM M accepts w for some M}
    (the acceptance problem for TMs)
  - The halting problem
  - {w | w is a description of a TM that
         halts on the empty input}

Not even recognizable:
  - The complement of the halting problem
  - {w | w is a description of a TM that
         does NOT halt on the empty input}

Why This Matters

Decidability tells you the fundamental limits of computation. If a problem is undecidable, no algorithm — no matter how clever — can solve it. This isn't about hardware limitations or slow computers. It's a mathematical proof that certain problems have no solution.

Recognizability is the middle ground. You can sometimes detect the answer (when it's "yes"), but you can't always determine the answer (when it's "no"). This has practical implications: some problems can be solved "most of the time" but not guaranteed to halt.

Analogy:
  Decidable: A friend who always answers your texts
  Recognizable: A friend who replies when they're free,
                but might never reply if they're busy
  Not recognizable: A friend who might never reply at all,
                    even when they're free