Decidability and Undecidability

Some problems have no algorithm at all, no matter how much time or memory is allowed. This lesson shows why, and how to recognise such problems.

There are more languages than machines

Every TM can be written as a finite string, so the TMs can be listed one by one: there are countably many. But the languages over {0, 1} are all subsets of the countable set Σ*, and there are uncountably many of them (Cantor's diagonal argument). So most languages are not recognised by any TM, not even as RE languages. The interesting question is which natural problems fall outside.

The halting problem

HALT_TM = { ⟨M, w⟩ : TM M halts on input w }

Proof by contradiction. Suppose a TM H decides it: H(⟨M, w⟩) always halts, answering "yes" if M halts on w and "no" otherwise. Build a new machine D that uses H on a machine's own description:

D(⟨M⟩):
    if H(⟨M, ⟨M⟩⟩) says "M halts on its own description":
        loop forever
    else:
        halt

Now run D on its own description ⟨D⟩:

• If D halts on ⟨D⟩, then H says "halts", so D loops forever. Contradiction.
• If D loops on ⟨D⟩, then H says "does not halt", so D halts. Contradiction.

Either way we have a contradiction, so H cannot exist. This is a diagonal argument: D is built to differ from every machine M on the input ⟨M⟩.

HALT_TM is recursively enumerable: a universal TM simulates M on w and accepts if the simulation halts. So:

• HALT_TM and A_TM = { ⟨M, w⟩ : M accepts w } are RE but not recursive.
• Their complements are not RE (if both a language and its complement were RE, it would be recursive).

Reductions

To show that a new problem B is undecidable, reduce a known undecidable problem A to it: give an algorithm that turns every instance x of A into an instance f(x) of B, with x ∈ A ⟺ f(x) ∈ B. Written A ≤ B.

The direction matters: reduce from the known hard problem to the new one. Reducing the new problem to a hard one proves nothing.

Example: E_TM = { ⟨M⟩ : L(M) = ∅ } is undecidable. Given ⟨M, w⟩, build a machine M′ that ignores its own input and runs M on w, accepting if M accepts. Then L(M′) is Σ* if M accepts w and ∅ otherwise. A decider for emptiness would therefore decide A_TM.

Rice's theorem

• "Property of the language" means it depends only on L(M), not on how M is built: "L(M) is empty", "L(M) is finite", "L(M) is regular", "L(M) contains 'abc'", "L(M) = Σ*".
• "Non-trivial" means some TMs have the property and some do not.

Rice's theorem does not apply to properties of the machine itself: "M has more than 5 states" or "M moves left at least once on input ε within 100 steps" are decidable, because they can be checked directly.

Post's correspondence problem

Given a list of dominoes, each with a string on top and a string at the bottom, is there a sequence of dominoes (repetition allowed) in which the top strings and the bottom strings spell the same word? PCP is undecidable, even though every single candidate sequence is easy to check. Because it involves only strings, PCP is the usual starting point for proving grammar problems undecidable, such as ambiguity of CFGs and emptiness of the intersection of two CFLs.

Decidable or not? A summary

(D = decidable, U = undecidable.)

Other famous undecidable problems: whether a program has an infinite loop, whether two programs compute the same function, Hilbert's tenth problem (does a polynomial equation have an integer solution?), and the totality problem (does M halt on every input?), which is not even RE or co-RE.

Practice questions