Comp 200 Lecture
The Halting Problem

Recap

Last time we saw that Monkey-Puzzle was "NP-complete" -- that is, if you could solve Monkey-Puzzle, you can actually solve any problem where purported-solutions-can-be-efficiently-verified.

Beyond NP

You might be wondering, what is a problem which isn't in NP? Can't all purported answers always be efficiently checked?

An Unsolvable Problem

But it gets worse! Some problems are provably intractable, while some others are provably unsolvable!

You might have typed a function in Scheme, which ended up having an infinite loop. For example, 

(define (f x)
   (* 2 (f (- x 1))))
You try (f 2), and wait, and wait, ... Running the stepper, we find that (f 2) = (* 2 (f 1)) = (* 2 (* 2 (f 0))) = (* 2 (* 2 (* 2 (f -1)))) = (*2 (* 2 (* 2 (* 2 (f -2))))) = ... Other even more succinct infinite loops might be 
;; (f x): number -->  ???? NEVER RETURNS!
;;
(define (f x)
  (f x))


;; (loop): --> ???? NEVER RETURNS
;; (note how this function takes no inputs.)
;; A rather pathological function!
;;
(define (loop)
  (loop))
After waiting 10min for an answer, you might have wished there had been a button, up next to "check syntax", which read "check for infinite loops". As it turns out, It is impossible for DrScheme to have such a button which would work for any program.

The halting problem: 

;; (halts? P I) : Program, Input --> boolean.
;; Returns whether or not evaluating (P I) will ever returns an answer.
;;
(define (halts? P I)
   ...)
That is, What program have we seen that takes in a function, and evaluates it? DrScheme! (Question: why doesn't "have Halts? just emulate P" work?)
[There is actually a subtle distinction going on here, between the function and the representation of the function. But note in scheme, functions are just lists which happen to have 'define as their first item and a two-element list as their second item. Indeed, DrScheme lets you type in such a list, and then evaluates it.]

So, if it were possible to write Halt?, then we could write: 

;; (twisted P): Program --> false-or-loop-forever
;;    If (P P) halts, then we loop forever;
;;    If (P P) runs forever, we'll halt and return "false".
;;
(define (twisted P)
  (if (Halts? P P)
      (loop)
      false))
That is, Now, the question is, what is (twisted twisted)? Uh-oh! This is a (proof by) contradiction; the only way to resolve the problem is to realize "Assume it's possible to write Halts?" is a faulty assumption:
It's impossible to ever write Halts?!. Yowza!

Other Unsolvable Problems

We can reduce halt? to other problems:
For instance, halt? reduces to halt-on-seven?: That is, a friend has opened Ye Olde Halt-on-seven Shoppe. You want to open up a Ye Olde Halting Problem Shoppe; that is, people come to you with a P and an I: 
      ;; Here is what your customer gives you:

      ;; (P inpt): any --> any-or-loop
      ;;
      (define (P inpt) ...)
      (define I ...)
You need to write a program my-program, which you can bring to your friend's shop: 
      ;; (my-program n): number --> any-or-loop
      ;; I need to concoct some program,
      ;; find out whether my program halts when given seven,
      ;; and somehow have this relate to whether (P I) halted! 
      (define (my-program n)
          ...???...)
          ; Note that my code can mention P and I.
          ; Hint: my code doesn't HAVE to use its input n (!)
Now, you need to determine whether your customer's P halts when given I, but you're allowed to find out whether my-program halts on seven. Upshot: Halt? <= Halt-on-seven?, and yet Halt? is infinitely difficult. Thus, we conclude ...(what?).. .

There are other undecidable problems which don't seem to be so obviously self-referential via computing:
Tiling:

We can reduce any of these problems to each other -- they're all equally unsolvable.

And now, beyond infinity: There are even higher levels of undecidability:

What does it mean, to say they are even more undecidable than Halt?? Even if we did have a magic oracle which would give us the answer to Halts?, we still couldn't compute these problems!
In fact, there are problems even more difficult than these!
...And even more than those!
...And in between each of these groups, there are others! (We say, these classes or problems are "dense", like the rational numbers on the number line. This is also the case with the classes between P and NP.)