[Overview] [Previous] [Next]

Reduction to the Halting Problem

To reduce problem X to the Halting Problem:

The state-entry problem

(I prefer to think of this as the dead code problem.) The problem is to determine whether Turing machine M, when given input w, ever enters state q.

The only way a Turing machine M halts is if it enters a state q for which some transition function delta(qi, ai) is undefined. Add a new final state Z to the Turing machine, and add all these missing transitions to lead to state Z.

Now use the (assumed) state-entry procedure to test whether state Z is ever entered when M is given input w. This will reveal whether the original machine M halts. We conclude that it must not be possible to build the assumed state-entry procedure.

Copyright 1996 by David Matuszek
Last modified Apr 14, 1996