Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 59 · Decidability and Computability

Reductions, Rice's Theorem and the Post Correspondence Problem

Prove problems undecidable by reduction from the halting problem, learn Rice's theorem on semantic properties, and explore the Post Correspondence Problem in Python.

After the halting problem, we do not want to repeat the diagonal argument for every new question. Instead we use a much more convenient tool: the reduction. To show that a new problem B is undecidable, we show that if B were decidable, then the halting problem would be decidable too. Since the latter is impossible, so is the former.

How a reduction proves undecidability

Known hard Start from a problem proved undecidable, like A_TM.
Transform Write a computable map from its instances to yours.
Contradict A decider for yours would decide A_TM.

Reductions transfer hardness from known problems to new ones.

1 / 2

Mapping reductions

A mapping reduction from A to B, written A ≤_m B, is a computable function f that turns every instance x of A into an instance f(x) of B such that

x ∈ A ⟺ f(x) ∈ B.

The function must be total and computable, which means a Turing machine that always halts computes it. Then:

  • If A ≤_m B and B is decidable, then A is decidable (compute f(x), ask the decider for B).
  • Contrapositive: if A ≤_m B and A is undecidable, then B is undecidable.
  • Likewise, if B is RE then A is RE, and if A is not RE then B is not RE.

In every undecidability proof the direction matters: you reduce from the known undecidable problem to the new one.

Example: emptiness of a Turing machine

E_TM = { ⟨M⟩ : L(M) = ∅ }. We reduce A_TM to the complement of E_TM (a decider for E_TM would also decide its complement).

Given ⟨M, w⟩, compute the description of a new machine M':

M' on input x: ignore x; run M on w; if M accepts, accept.

Then:

  • if M accepts w, M' accepts every input, so L(M') ≠ ∅;
  • if M does not accept w, M' accepts nothing, so L(M') = ∅.

So ⟨M, w⟩ ∈ A_TM ⟺ ⟨M'⟩ ∉ E_TM. The function ⟨M, w⟩ ↦ ⟨M'⟩ is computable: it just writes down a program text. We never run M' during the reduction, which is the key point: reductions build machines, they do not execute them.

The next demo builds M' with Python closures and tries to find an accepted input with a bounded search:

Python The reduction from A_TM to emptiness

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If an algorithm could decide whether L(M') is empty, we could use it on ⟨M'⟩ to decide whether M accepts w, which we know is impossible. So E_TM is undecidable. Note one more thing: E_TM is not RE, but its complement is RE (search for an input that M accepts, dovetailing).

More reductions, same pattern

The same trick works for many properties: in each case build M' whose language depends on whether M accepts w.

Problem The machine M' built from ⟨M, w⟩ Why it works
REGULAR_TM: is L(M) regular? on x: accept if x = 0^n 1^n; otherwise run M(w) and accept if it accepts if M accepts w, L(M') = everything (regular); else L(M') = {0^n 1^n} (not regular)
ALL_TM: does M accept every string? on x: run M(w); accept if it accepts L(M') = all or nothing
FINITE_TM: is L(M) finite? on x: run M(w); accept if it accepts L(M') = infinite or empty
EQ_TM: do two machines accept the same language? compare M' against a machine that accepts nothing reduces from E_TM

Every one of these questions asks about the language that a machine accepts, not about how it works. That observation leads to a general theorem.

Rice's theorem

A property of languages is non-trivial if some RE languages have it and some do not. For a property P, the set { ⟨M⟩ : L(M) has property P } is the language of machines whose language has P.

Rice's theorem. Every non-trivial property of the languages recognized by Turing machines is undecidable.

In plain words: you cannot decide anything interesting about what a program computes by looking at its code. Examples of undecidable questions:

  • Is the language of this program empty? Finite? Regular? Context-free?
  • Does it accept the string "hello"? Does it accept all strings?
  • Is the function it computes total? Is it the identity function?
  • Do these two programs compute the same function?

Why it holds (sketch). Suppose P is non-trivial and the empty language does not have P (otherwise use the complement of P). Pick a machine M_P whose language has P. Given ⟨M, w⟩, build M': on input x, first run M on w; if it accepts, run M_P on x and answer as M_P does. Then L(M') equals L(M_P) (which has P) if M accepts w, and ∅ (which does not) otherwise. A decider for P would decide A_TM.

Rice's theorem covers semantic (behavioral) properties only. Properties of the machine's structure are often decidable: does this machine have fewer than 5 states?, does its code contain the instruction x := 0?, does it halt within 100 steps? The theorem says nothing about those.

This is why static analyzers, antivirus programs and compilers cannot be perfect: "does this program ever do something bad?" is a semantic property. They necessarily give up on some programs, accept false alarms or miss real problems.

The Post Correspondence Problem (PCP)

The Post Correspondence Problem shows that undecidability is not only about machines. You are given a finite set of dominoes, each with a string on top and a string on the bottom, for example (b / bbb), (babbb / ba), (ba / a). You may use each domino any number of times. The question: is there a sequence of dominoes (at least one) such that the string formed by the tops equals the string formed by the bottoms?

For these three dominoes, using dominoes 2, 1, 1, 3 gives top babbb·b·b·ba and bottom ba·bbb·bbb·a; both read babbbbbba. A solution exists. But in general no algorithm can decide whether a solution exists (Post, 1946, by a reduction from computation histories of Turing machines). PCP is semi-decidable: a breadth-first search finds a solution if one exists, but cannot prove that none does.

Python Searching for PCP solutions (semi-decision)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first two instances are solved quickly. For the third, the top is always shorter than the bottom, which a human can prove impossible, but the program only knows that nothing was found within the depth limit. For other instances the shortest solution is astronomically long, and no limit would ever be enough. That gap is the undecidability.

A map of the landscape

Problem Decidable? RE? Co-RE?
A_DFA, E_DFA, EQ_DFA, A_CFG, E_CFG yes yes yes
A_TM, HALT no yes no
E_TM no no yes
EQ_TM, ALL_TM no no no
PCP no yes no
EQ_CFG, ALL_CFG no no yes
CFG ambiguity no yes no
Hilbert's tenth problem (integer solutions of polynomial equations) no yes no

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. To prove that a new problem B is undecidable by reduction, which direction must the reduction go?

    If a decider for B existed, composing it with the reduction would decide the known undecidable problem.
  2. 2. In the reduction from A_TM to E_TM, what language does M' have if M does not accept w?

    M' accepts only after M accepts w; otherwise it never accepts anything.
  3. 3. What does Rice's theorem say?

    Rice's theorem is about semantic properties of what a program computes, not syntactic properties of its code.
  4. 4. Which of these questions is decidable?

    A bounded simulation always finishes; the other questions are semantic properties covered by Rice's theorem.

Summary

  • A mapping reduction A ≤_m B transfers decidability downward and undecidability upward.
  • Reductions construct a new machine M' from ⟨M, w⟩ whose behavior depends on whether M accepts w.
  • E_TM, REGULAR_TM, ALL_TM, FINITE_TM and EQ_TM are undecidable.
  • Rice's theorem: every non-trivial semantic property of a program's language is undecidable.
  • PCP is an undecidable problem with no machines in its statement; it is semi-decidable by search.

Next: Computable functions and the busy beaver