Hacker News new | ask | show | jobs
by joshuakgoldberg 1460 days ago
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.
2 comments
Gehinnn 1460 days ago
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).

link
tadfisher 1460 days ago
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.
link