[Haskell] The GHC typechecker is Turing-complete

Josef Svenningsson 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:
http://www.lochan.org/keith/publications/undec.html

All the best,

/Josef


More information about the Haskell mailing list