Decidability and Halting Problem

Decidability and the Halting Problem

Decidability

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.

The Halting Problem

Statement: Given an arbitrary Turing machine $M$ and an input string $w$, decide: Does $M$ halt when run on $w$?

$$\text{HALT} = {\langle M, w \rangle : M \text{ halts on input } w}$$

Theorem (Turing, 1936): The Halting Problem is undecidable.

Proof by Contradiction

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$:

• If $H(D, D)$ accepts (i.e., $D$ halts on $\langle D \rangle$): then $D$ loops forever. Contradiction.
• If $H(D, D)$ rejects (i.e., $D$ loops on $\langle D \rangle$): then $D$ halts. Contradiction.

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.

Semi-decidability

HALT is semi-decidable: run $M$ on $w$; accept if it halts. But there is no way to detect looping.

Practical Implications

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.