[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.

Copyright © 1996 by David Matuszek

Last modified Apr 14, 1996