in reply to Perl Cannot Be Parsed: A Formal Proof
Type inference (and as a consequence parsing?) in ML 'and I suspect many other functional languages, is complete in deterministic expotential time. For any practical reasons that's as close to undecidability as possible.
In Section
Meditations