Exercise 4.15.  Given a one-argument procedure p and an object a, p is 
said to ``halt'' on a if evaluating the expression (p a) returns a value 
(as opposed to terminating with an error message or running forever). 
Show that it is impossible to write a procedure halts? that correctly 
determines whether p halts on a  for any procedure p and object a. Use 
the following reasoning: If you had such a procedure halts?, you could 
implement the following program:

(define (run-forever) (run-forever))

(define (try p)
  (if (halts? p p)
        (run-forever)
              'halted))

Now consider evaluating the expression (try try) and show that any 
possible outcome (either halting or running forever) violates the 
intended behavior of halts?.

————————————————————————————————————————————————————————————————————————

Whee!

(try try) will either halt or run forever.

If it halts, then (if (halts? p p)) must have taken the second branch, 
i.e. (halts? p p) must have returned false.  According to the definition 
of halts?, if (halts? p p) returns false, then p called with input p 
must not halt.  In this case p is equal to try itself, which means that 
(try try) must halt, which is a contradiction.

If (try try) runs forever, then it must be either because (halts? p p) 
runs forever, or because (halts? p p) returned true, and (run-forever) 
was called.  If (halts? p p) runs forever, then halts? does not meet the 
definition given, so only the second possibility remains.  If (halts? p 
p) returned true, then, since p here is try itself, this must mean that 
(try try) would halt, which again is a contradiction.