[Haskell] The GHC typechecker is Turing-complete

[keithw at lochan.org]

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 at 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-)