[Haskell-cafe] Slightly off-topic: Lambda calculus
keithshep at gmail.com
Sun Jun 21 13:18:42 EDT 2009
scratch that... it's completely wrong
On Sun, Jun 21, 2009 at 1:09 PM, Keith Sheppard<keithshep at gmail.com> wrote:
> 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