[Haskell] The GHC typechecker is Turing-complete

keithw at lochan.org keithw at lochan.org
Fri Aug 18 17:59:26 EDT 2006

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


--KW 8-)

More information about the Haskell mailing list