On Fri, Aug 11, 2006 at 08:30:15AM -0400, Robert Dockins wrote:
On Aug 11, 2006, at 7:40 AM, Josef Svenningsson wrote:
On 8/11/06, Robert Dockins <robdockins@fastmail.fm> wrote:
My purpose today is to show that the GHC typechecker with multi- parameter typeclasses, functional dependencies, and undecidable instances is Turing- complete. Some time ago on this mailing list, there was a brief
Here's a link that works: http://www.lochan.org/keith/publications/undec.html
Ah, thanks. This is interesting because it doesn't even require functional dependencies. OTOH, he uses code generation techniques to create the TMs in the first place...
Thanks Josef - I'm not on this list as much as I'd like any more. The code generation techniques aren't essential, they just allow you to specify the TMs in a more pleasant notation. Robert, your coding is definitely nicer, since you can write SK terms directly in the usual notation (and SK is nicer than TMs anyway, especially for us FPers). Cheers, --KW 8-)