CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: The Halting Problem

1. Question: can we automatically verify any arbitrary Python program P works properly?
   • This is really important! Programs control our cars and planes and banks and nuclear weapons and most everything else. It would be just lovely if we could be sure they actually worked right.
   • When these programs fail, the stock market flash-crashes, planes crash, and people die. This is very serious business.
2. Restated: given a program P and an arbitrary input W, does P(W) eventually halt (and not run forever), and then does it return the correct result?
3. Let's just focus on the first part: does P(W) even halt at all (ignoring whether or not it returns the correct result)? This is the Halting Problem.
4. Aside: we know Python programs can take other Python programs as input. Consider our linter, our autograder, and Python itself.
5. Assume we have a function Halts(P, W) that halts if program P halts on input W. Then we write this perfectly-valid Python function:
   

       def K(P):
           if (Halts(P, P)):
               while True: pass # run forever
           else:
               return 42 # halt!
   

6. Now, what happens when we call K(K)?
   • If Halts(K,K) is True, then K(K) hangs (runs forever)
   • If Halts(K,K) is False, then K(K) halts
   • So either way, Halts(K,K) is wrong.
   • Thus, the Halts function cannot exist!
7. So: the Halting Problem is uncomputable
8. So: we cannot tell if arbitrary programs work.
9. Though we can tell if some programs work. See here.
10. You can even win a Turing Award for this! See here.
11. The race is on to prove more and more programs work, but the Halting Problem guarantees we will never prove that they all work.