[Haskell] The GHC typechecker is Turing-complete
josef.svenningsson at gmail.com
Fri Aug 11 07:40:23 EDT 2006
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 discussion
> about a lambda calculus and a direct Turing-machine implementation; either
> would be sufficient to demonstrate the Turing-completeness of the typechecker.
> However, neither implementation was preserved on-list, and the links are
> now dead.
Here's a link that works:
All the best,
More information about the Haskell