[plt-scheme] Check for function equality?

From: David Van Horn (dvanhorn at ccs.neu.edu)
Date: Thu Feb 19 19:59:18 EST 2009

John Clements wrote:
> 
> On Feb 19, 2009, at 3:34 PM, Robby Findler 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]))
> 
> ... looks to me like this is just a teensy more complex than it needs to 
> be.  How about:
> 
> (define (als-program x)
>   (cond
>     [(halts? x x) (loop-forever)]
>     [else 3]))
> 
> (define (loop-forever) (loop-forever))
> 
> ?
> 
>> and ask what is
>>
>>  (als-program als-program).

Uh..... maybe I'm being stupid; I don't see a contradiction following 
from this.

If (halts? als als), then (als als) loops.
If not (halts? als als), then (als als) is 3.

Robby's setup leads to a contradiction though.

David




Posted on the users mailing list.