[Haskell-cafe] Slightly off-topic: Lambda calculus

[Keith Sheppard]

forgot to cc the cafe :-)

On Sun, Jun 21, 2009 at 1:08 PM, Keith Sheppard<keithshep at gmail.com> wrote:
> hmm, it's been a while but...
>
> i think this "infinite loop" with a free variable would cause collision
>
> (\a . a a) (\b . b b d)
>
> On Sun, Jun 21, 2009 at 12:53 PM, Andrew
> Coppin<andrewcoppin at btinternet.com> wrote:
>> OK, so I'm guessing there might be one or two (!) people around here who
>> know something about the Lambda calculus.
>>
>> I've written a simple interpretter that takes any valid Lambda expression
>> and performs as many beta reductions as possible. When the input is first
>> received, all the variables are renamed to be unique.
>>
>> Question: Does this guarantee that the reduction sequence will never contain
>> name collisions?
>>
>> I have a sinking feeling that it does not. However, I can find no
>> counter-example as yet. If somebody here can provide either a proof or a
>> counter-example, that would be helpful.
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
>
> --
> keithsheppard.name
>



-- 
keithsheppard.name