[Haskell] The GHC typechecker is Turing-complete
robdockins at fastmail.fm
Fri Aug 11 08:30:15 EDT 2006
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-
>> typeclasses, functional dependencies, and undecidable instances is
>> complete. Some time ago on this mailing list, there was a brief
>> about a lambda calculus and a direct Turing-machine
>> implementation; either
>> would be sufficient to demonstrate the Turing-completeness of the
>> However, neither implementation was preserved on-list, and the
>> links are
>> now dead.
> Here's a link that works:
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...
> All the best,
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
More information about the Haskell