A problem is decidable if there exists a Turing machine that:
- Halts and accepts for every YES instance
- Halts and rejects for every NO instance
A problem is undecidable if no such Turing machine exists — no algorithm can solve it correctly for all inputs.
Examples of decidable problems:
- Is a given number even?
- Does a string contain the letter ‘a’?
- Does a context-free grammar generate a given string?
KEY TAKEAWAY: Decidability asks whether a problem can be solved by any algorithm at all. Undecidability is a fundamental limit, not a current technology limitation.
Statement: Given an arbitrary Turing machine \(M\) and an input string \(w\), decide: Does \(M\) halt when run on \(w\)?
Theorem (Turing, 1936): The Halting Problem is undecidable.
Assume a Turing machine \(H\) exists that solves HALT:
\$\(H(\langle M, w \rangle) = \begin{cases} \text{accept} & \text{if } M \text{ halts on } w \\ \text{reject} & \text{if } M \text{ loops on } w \end{cases}\)\$
Construct a new machine \(D\) using \(H\) as a subroutine:
D(input M):
if H(M, M) accepts: # Does M halt on its own description?
loop forever
else:
halt and accept
Now run \(D\) on its own description \(\langle D \rangle\):
In both cases there is a contradiction. Therefore \(H\) cannot exist. \(\square\)
This argument is a diagonal argument, originally due to Cantor.
EXAM TIP: You do not need to reproduce the full formal proof. Know the key steps: assume \(H\) exists, construct \(D\) that does the opposite, derive the contradiction. Name this as proof by contradiction.
| Class | Halts on YES? | Halts on NO? |
|---|---|---|
| Decidable | Yes | Yes |
| Semi-decidable | Yes | Not always |
| Undecidable | Not always | Not always |
HALT is semi-decidable: run \(M\) on \(w\); accept if it halts. But there is no way to detect looping.
| Consequence | Explanation |
|---|---|
| No perfect infinite-loop detector | Cannot write a general program to detect all infinite loops |
| No perfect virus scanner | A perfect scanner would solve the Halting Problem |
| No general program verifier | Cannot automatically verify all program correctness |
COMMON MISTAKE: Undecidable does NOT mean “unsolved so far.” It means that no algorithm can ever solve it for all inputs — this is a proved mathematical fact.
VCAA FOCUS: State the Halting Problem. Outline the proof by contradiction (assume \(H\) exists, build \(D\), derive contradiction). Know that undecidability represents a hard limit of computation, distinct from the soft limits of NP-Hard problems.