Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

The reduction builder

Hopcroft 2e §8.1.3. Once one problem is known to have no algorithm, every later proof can borrow from it. Take an instance of the hard problem, build from it an instance of the new problem with the same answer, and an algorithm for the new problem would have solved the hard one. Since nothing solves the hard one, nothing solves the new one either.

The direction is the part students lose marks on, so it is enforced here rather than explained. A reduction must run from a problem already known to be undecidable to the new one. Turn it around and the statement you prove is “if the new problem is decidable, then the hard one is” — true, and useless, because its conclusion is already known to be false. Pick a decidable problem as the source and this page will say so instead of drawing a diagram.

Which source you start from also decides what you have proved (§9.2.4, p. 380). A reduction from Lu shows a problem is not recursive and says nothing about whether it is RE. Only a reduction from Ld can show a problem is not RE at all — and Lu, being RE itself, is no use for that.

Start from a problem already known to be undecidable

P₁ in Fig. 8.7 — the hard problem whose hardness is being carried across.

Show that this one is undecidable too

P₂ in Fig. 8.7 — the new problem, about which nothing is assumed.

Building The hello-world problem ≤ The calls-foo problem: if there were an algorithm for the calls-foo problem, there would be one for the hello-world problem.

Narration

Start from a problem already known to be undecidable. The hello-world problem: Does program P, given input I, print hello, world as the first thing it prints? A tester H would let us build H₂, which prints hello, world when given itself as input exactly when it does not. The contradiction is §8.1.2, and it is where every other undecidability result in the chapter starts.

Hopcroft 2e, §8.1.2

instance of The hello-world problemConstructinstance of The calls-foo problemDecideyes / no
Fig. 8.7. The dashed box is the algorithm assumed to exist. Step to the end to see why it cannot.