Computer Science 15-110, Fall 2009
Class Notes:  The Halting Problem

In class today, we explored the Halting Problem.  After discussing what it is, we provided some intuition that the problem is unsolvable by demonstrating how we could use the solution to the halting problem to prove or disprove Goldbach's Conjecture (and Fermat's Last Theorem, etc).

We then actually proved the halting problem.  To do so, we first used diagonalization to prove that there are more real numbers than there are integers (technically, |R| > |Z|).  We then repeated this technique to prove that if you had written a Java method that "solves" the halting problem, then we can use that method to write a Java program that does the opposite of itself -- it halts if it hangs and hangs if it halts.  This is impossible, of course, thus completing our proof by contradiction.

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem