[Haskell-cafe] Slightly off-topic: Lambda calculus
keithshep at gmail.com
Sun Jun 21 13:09:39 EDT 2009
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
More information about the Haskell-Cafe