Hacker News Reader

TypeScript's type system is Turing Complete: meaning it has conditional branching (conditional types) and works with an arbitrary huge amount of memory. As a result, you can use the type system as its own programming language complete with variables, functions, and recursion. This blog post is a starting list of a bunch of the shenanigans TypeScript developers have pushed the type system to be able to do.

View on HN

That's not the meaning of turing completeness, just an implication of the space hierarchy theorems. There are systems that also have branching and unbounded memory, but are not turing complete. Context free grammars for example.

Turing completeness means for TS that for every computable function, there is a TS type that can compute that function (if TS wouldn't limit the recursion depth).

It also makes static checking undecidable in pathological cases. I know Idris has this problem as well; they work around it by skipping partial functions in types, so you end up with "total" and "partial" programs where only the former are completely typechecked proofs.

Reply on news.ycombinator.com