Decidability

A problem is decidable if some Turing machine always halts with the correct yes/no answer.

The Halting Problem

Given a TM M and input w, does M halt on w? This is undecidable.

Proof sketch (diagonalization):
Suppose H(M, w) decides halting.
Build D(M):  if H(M, M) says "halts" then loop forever, else halt.
Run D(D):
  If D(D) halts → H says halts → D loops.   Contradiction.
  If D(D) loops → H says loops → D halts.   Contradiction.
So H cannot exist.

Decidability Summary

D = decidable, UD = undecidable

Rice's Theorem

Every non-trivial property of the language recognised by a Turing machine is undecidable. For example, "Is L(M) empty?" and "Is L(M) regular?" are both undecidable.

Post Correspondence Problem (PCP)

Given pairs of strings (xᵢ, yᵢ), is there a sequence i₁…iₖ with x_{i₁}…x_{iₖ} = y_{i₁}…y_{iₖ}? PCP is undecidable and is often used to prove other CFG problems undecidable, such as ambiguity.