### Halting Problem -- Simple Proof

**This web-page is copied from lecture notes for cs1510 of
Prof Kirk Pruhs of the Dept of Computer Science, University of Pittsburg.
The original url for this page is
http://www.cs.pitt.edu/~kirk/cs1510/notes/halt/halt.html.**

**Next:**
About this
document

The Halting Problem is:

INPUT: A string *P* and a string *I*. We will think of *P* as
a program.

OUTPUT: 1, if *P* halts on *I*, and 0 if *P* goes into an
infinite loop on *I*.

Theorem (Turing circa 1940): There is no program to solve the Halting
Problem.

Proof: Assume to reach a contradiction that there exists a program
Halt(*P*, *I*) that solves the halting problem, Halt(*P*,
*I*) returns True if and only *P* halts on *I*. The given this
program for the Halting Problem, we could construct the following string/code
*Z*:

Program (String x)
If Halt(x, x) then
Loop Forever
Else Halt.
End.

Consider what happens when the program *Z* is run with input
*Z*
Case 1: Program *Z* halts on input *Z*. Hence, by the correctness
of the Halt program, Halt returns true on input *Z*, *Z*. Hence,
program *Z* loops forever on input *Z*. Contradiction.

Case 1: Program *Z* loops forever on input *Z*. Hence, by the
correctness of the Halt program, Halt returns false on input *Z*, *Z*.
Hence, program *Z* halts on input *Z*. Contradiction.

End Proof.

One can now show that there is no program for some new problem problem
*U* by showing that , i.e. Halting is reducible
to *U*.

*Kirk Pruhs *

Mon Nov 3 15:30:13 EST 1997