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