[plt-scheme] Check for function equality?

Technically it was Jacob's setup from a lecture he gave one year in my
HtDP course (I've been using it ever since, tho :).

But lets not give away the answer until people have time to think
about it ... after all, I know many readers have seen this before.

Robby

On Thu, Feb 19, 2009 at 6:59 PM, David Van Horn <dvanhorn at ccs.neu.edu> wrote:
> 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
>
>
>