[Overview] [Previous] [Next]

Reduction to the Halting Problem

To reduce problem X to the Halting Problem:

• Assume that you have an effective procedure (Turing machine or any other kind of algorithm) to solve problem X.
• Show how to use the program for X to solve the Halting Problem.
• Conclude that problem X can't be solved.

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 (q_i, a_i) 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.