[plt-scheme] Check for function equality?

On Thu, Feb 19, 2009 at 6:34 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> One can explain this without resort to Turing machines or other automata!
>
> Here's how you might do it.
>
> Imagine you had a function called "halts":
>
>  ;; halts? : program input -> boolean
>  ;; returns true when the program halts on the given input
>  ;; returns false when the program would fail to halt on the given input
>  ;; always returns something.
>
> Now consider this function:
>
>  (define (als-program x)
>    (cond
>      [(halts? x x) (als-program x)]
>      [else 3]))
>
> and ask what is
>
>  (als-program als-program).
>

Well stated for you Dave. I encourage you to answer Robby's question.
After thinking about (als-program als-program), ask yourself what
(halts? als-program als-program) returns. The first time I saw this as
an undergrad, I thought it was sick to resort to such trickery. It
actually is, however, quite elegant. Such a trivial looking function
leads to profound ideas. :-)

-- 

Cheers,

Marco