15-110 Spring 2011
Honors/Bonus Notes:  Countability / The Halting Problem

• Topics
• Part 1:  Countability and Diagonalization Proofs
• A set S is "countable" if there exists a bijection between the set's elements and the positive integers.  We write |S| = |Z⁺|.  However, since |Z| = |Z⁺|, we can just write |S| = |Z|.
• We found that |Z| = |Evens| = |Primes| = |Powers of 10| = |Powers of 10¹⁰⁰⁰⁰|.
• We then went the other way, trying to find a set larger than |Z| (that is, an uncountable set), but we found...
• |Z| = |Q (the rationals)| = |Z² (pairs of integers)| = |Z¹⁰⁰⁰⁰|
• Since |Powers of 10¹⁰⁰⁰⁰| = |Z¹⁰⁰⁰⁰|, it sure seems like this is nonsense, and all infinite sets are |Z|.  But...
• We then proved |R (reals)| > |Z|
• Diagonalize:
• If we can count every real # from 0 to 1, then we can list them in a specific order (that's what counting means, after all)
• We can use this list to construct a new real # between 0 and 1.  How?  To find the kth digit of our new number, we'll ask for the kth real number, and then find that numbers kth digit, and then change it.
• In this way, we constuct a new real number that cannot possibly be in the table.
• But our new number is a real number between 0 and 1.  So the table is incomplete.  So the reals are not countable.  So |R| > |Z|.  So there is more than one infinity.  Wow!!!
• We then defined 2^S = PS(S) = The Power Set of S = The set of all subsets of S
• So, for example, PS(Z) = { all subsets of Z } = { {evens}, {primes}, {powersOf10}, {perfectNumbers}, ... }
• We then proved |2^S| > |S| for any countable set S
• Diagonalize:
• List the counted subsets down the left-hand side of  a table, and the positive integers along the top; for each entry in the table, label it 1 if that integer is in that subset, or 0 otherwise.
• Construct a new subset by flipping the values on the diagonal.
• This is clearly a subset of the integers, yet it cannot be in the table, and so |2^S| > |S|.
  
  
• Part 2:  The Halting Problem
• Defined the Halting Problem:  given a program P and an input N, can we decide if P will ever halt on input N (that is, without actually running P on N and waiting to see if it ever halts, since then we could say yes if it halted, but we could never say no, since it could eventually halt...)
• We argued that there are countably many Python programs (well, we really restricted ourselves to Python functions of one variable, though the results generalize to arbitrary programs in arbitrary languages)
• Thus, there exists an invertible function mapping Python programs (functions of one variable) to the positive integers.
• Time to diagonalize...
• First, we assume that the Halting Problem has been solved, so that there exists a Python function halts(P,N), which returns True if program P halts on input N and False otherwise (if P hangs on input N).
• The rows of our table are the Python programs (functions of one variable).  The columns are the positive integers that can be input to those programs.
• We will then call halts(P,N) for every program P and every input N to fill out our table (we placed 1's where P halts on N and 0's where it hangs).
• Now, we diagonalize, constructing a Python function in one variable that for each input K, does the opposite of halts(K,K).  Actually, it's easy enough to write this function in Python:
       def haltsParadox(N):
            if (halts(N,N)):
                 while (True): pass  # hang
            else
                 return # halt
• The function above is a Python function in one variable, so it must be in our table.  Say it's function #K.  What happens when we call haltsParadox(K)?  If halts(K,K) is True, meaning it will halt, then it hangs, and vice versa!  This is impossible!
• So haltsParadox() cannot exist!
• But it's perfectly valid Python so therefore halts() cannot exist!
• And that's our proof:  you cannot solve the halting problem.  QED.
• We discussed (without mentioning Rice's Theorem by name) that this means you cannot prove that an arbitrary program is bug-free (though we discussed that you certainly can prove some programs to be bug-free), and discussed the broad implications of this fact.