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.

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.

 
• About this document ...