CMU 15-110: Principles of Computing
Computability and The Halting Problem

---

Note: while the talk in class included more details on this topic, these notes will focus on what you need to know for the quiz and the final:

---

• Intractable
  As we learned from last lecture, a problem is intractable if it can be solved, but unfortunately it may take too long to practically use that solution. Often, far too long, as in longer than the universe has existed. For example, using brute force to solve subsetSum works in theory but it is intractable.


• Uncomputable
  Even worse than intractable, a problem is uncomputable if it cannot be solved (in general) at all, no matter how much time we may allow to solve it.


• The Halting Problem
  This is the classic uncomputable problem. The Halting Problem asks this: given a program P (which you can think of as simply a Python function) and an input W, when we call P(W), does that call ever halt (stop running, and in Python's case, return a value) or will it hang (run forever, and in Python's case, never return a value)?


• Intuition that the Halting Problem cannot be solved
  We talked about Goldbach's Conjecture that every even number greater than 2 is the sum of two primes. So 4=2+2, 6=3+3, 8=3+5, and so on. This has been checked to vastly huge numbers, but so far nobody has been able to prove it.
  
  However, if we had a solution to the Halting Problem, we could easily use that solution to prove Goldbach's Conjecture! We would write a program P that ignored its input W, and just started checking every even number 4, 6, 8, 10,.... and verifying that it is the sum of two primes. If it ever found one that is not, it just halts and returns that number. If it never finds one, it hangs, and runs forever. We then ask if P(0) halts. If so, Goldbach's Conjecture is false (right?), otherwise Goldbach's Conjecture is true (right?).
  
  The same trick can be used to prove Fermat's Last Theorem, the Riemann Hypothesis, and other such problems!
  
  So? So solving the Halting Problem would give us solutions to lots of problems that have stumped the world's greatest mathematicians for centuries (though Fermat's Last Theorem was recently solved, woohoo!). Amazing!
  
  This is not a proof that we cannot solve the Halting Problem, it just provides some intuition that we may not be able to do so, or at the very least, doing so would be very hard to do, and the solution would be amazingly powerful.


• Proof that the Halting Problem cannot be solved
  We used diagonalization to prove the Halting Problem. You are not responsible for the details beyond what is included here. But you may want to read here for example about how Cantor used diagonalization to prove there are different sizes of infinity. Awesome! Goedel used a similar approach to prove the Incompleteness Theorem (see here) that basically concludes that math is unsound (actually wrong!) or incomplete (unable to prove some things that are in fact true). Astounding!
  
  Glossing over some details, our proof (the part you need to know) goes like this:
  1. Say you solved the halting problem! Then, to be specific, you have written a Python function Halts(P, W) that returns True if function P halts on input W.
  2. Then we will write this function that uses your Halts function:

     def doesTheOpposite(P):
           if (Halts(P, P) == True):
               # since P halts on itself, we will hang (run forever)
               while True: pass
           else:
               # since P hangs on itself, we will halt (return!)
               return 42
           

  3. Notice, importantly, that doesTheOpposite is a perfectly valid Python program (assuming Halts is, too).
  4. Now, what happens if we call doesTheOpposite on itself? That is, what if we do this:

     print( doesTheOpposite(doesTheOpposite) )

  5. We see that this call halts if it hangs, or hangs if it halts.
  6. But that is impossible. So this call is impossible!
  7. But the call is perfectly valid Python. So it is impossible to even write doesTheOpposite!
  8. But doesTheOpposite is perfectly valid Python. So it is impossible to write its one and only helper function, Halts.
  9. So the Halting Problem is uncomputable. QED.


• Consequences of the Halting Problem
  Seeing how computer programs control our cars, our money, our nuclear missiles, and on and on, we would love to be able to prove that these programs actually work.
  
  But... To prove that a program P works, we would need to prove that P(W) returns the right answer for all possible inputs W.
  
  But... Because of the uncomputability of the Halting Problem, we cannot even prove whether P(W) halts, let alone if it halts with the correct answer!
  
  So... Because of the Halting Problem, we cannot prove in general if programs work properly.
  
  Aside: the words "in general" are important there. We can prove that particular programs work, and much work (some of it resulting in Turing Awards!) is invested into expanding the space of such programs we can prove work properly. Still, we can never ever prove all of them. As of now, we can prove very very few of them.


• The Bottom Line
  
  • The Halting Problem is not computable
  • So, sadly, we cannot prove in general that programs actually work (we cannot even prove they in general even halt, let alone halt successfully)
  • But: the term "in general" gives us some modest hope, as we can prove some programs work properly, and maybe over time we can prove all the programs that matter (the ones we actually use) work properly. For now, though, that's just a dream.

---