Java Generics are Turing Complete

Turing completeness doesn't have to come from a single feature, it often comes from a combination of features. e.g. the interaction between subtyping (e.g. inheritance) and generics (with variance) is tricky: https://www.cis.upenn.edu/~bcpierce/papers/variance.pdf It can be highly nontrivial to tell if a language actually has a Turing complete type system: the 2007 Kennedy&Pierce paper made it likely that java was turing complete; but it took until 2016 until it was finally proven that to be turing complete (https://arxiv.org/abs/1605.05274). > What would it take a for a type system to NOT become Turing complete? An analysis of all possible interactions between all features in the type system, building a formal proof that the type system is not turing complete. This is not really realistic for the style of complex generic type systems that programmers are now used to, it would need to be a vastly simpler language.

> Rust’s type system ended up being Turing-complete anyway. It seems like it fell into the same trap as C++ templates: it’s an accidental programming language in a programming language, but with way worse syntax. Most anything in software can easily end up Turing-complete though. It isn't that high of a bar unfortunately. I think most mature type and template systems end up as Turing-complete. To single out Rust for this is to ignore that this is just standard fare for mature typing systems. TypeScript's types are Turing complete: https://github.com/microsoft/TypeScript/issues/14833 Python's type hints are Turing complete: https://arxiv.org/abs/2208.14755 Java generics are Turing complete: https://arxiv.org/abs/1605.05274

Types in TS are Turing Complete [1], so any static analysis you build ontop of that language is bound to be unsound or undecidable. You could argue this rarely occurs in practice, but I would prefer a type system that is incomplete but sound and decidable. Incidentally, this issue also affects Java, which is both unsound [2] and undecidable [3]. Kotlin does have a fairly complicated subtyping relation [4], which has caused similar issues in languages like Scala [5], however whether the same issue affects languages based on mixed use-site and declaration-site variance like Kotlin is still an open question and requires further investigation. [1]: https://github.com/microsoft/TypeScript/issues/14833 [2]: https://io.livecode.ch/learn/namin/unsound [3]: https://arxiv.org/abs/1605.05274 [4]: https://kotlinlang.org/spec/type-system.html#subtyping [5]: https://arxiv.org/abs/1908.05294

> but it's not true of generics in most languages not sure how true that is. * TypeScript: https://github.com/microsoft/TypeScript/issues/14833 * Rust: https://sdleffler.github.io/RustTypeSystemTuringComplete/ * Haskell (GHC): https://mail.haskell.org/pipermail/haskell/2006-August/01835... * Scala: https://michid.wordpress.com/2010/01/29/scala-type-level-enc... * Java: https://arxiv.org/abs/1605.05274

> There are exceptions of course for a definition of "exceptions" being "virtually all languages with a non-trivial static type system and non-zero userbase" as shown in your link. Java (https://arxiv.org/abs/1605.05274), C# (https://blog.hediet.de/post/how-to-stress-the-csharp-compile...), Scala (https://michid.wordpress.com/2010/01/29/scala-type-level-enc...), Haskell, Rust (https://sdleffler.github.io/RustTypeSystemTuringComplete/), Typescript (https://github.com/Microsoft/TypeScript/issues/14833) ... Having a type system with generics and not being turing-complete as a result is the exception, not the rule.

Actually, subtype-checking in Java is Turing-complete. Someone proved this and used the result to build a parser generator for fluent interfaces. [1] [1] https://arxiv.org/pdf/1605.05274.pdf

Java’s generics are Turing complete, though I don’t think anyone has written a useful program in them yet: https://arxiv.org/pdf/1605.05274.pdf

A related result is that java generics are Turing complete [1]. As a result you can write programs which will loop the type checker! I was at the popl presentation where the author showed this result. He gave a demo where he defined a Turing program and a tape, and then let the type checker give the answer (halting with 1 will succeed type checking, halting with 0 will give a type error). This was a lot of fun. [1] https://arxiv.org/pdf/1605.05274.pdf

So is Java's type system [1], and Rust's and Haskell's with some modest extensions, and Scala's. Many type systems have turned out to be Turing complete. [1] https://arxiv.org/abs/1605.05274

Turing complete systems are highly capable, and thus, are harder to prove anything about. The halting problem notwithstanding, there's first the "there are things that don't halt" problem: that is, you can write a valid TypeScript program that will never finish compiling. Now, this really shouldn't be an issue unless someone is deliberately abusive. Java's generic types are also Turing complete[0], and it hasn't been problematic. Just because an abusive program exists doesn't mean it will be written. But who am I kidding... this is the JavaScript community. I'll give it 2 weeks until someone releases a framework allowing you to write functions that don't compile unless their input is a prime number. [0] https://arxiv.org/pdf/1605.05274.pdf

> I mean; C++ templates are Turing complete. that's not a very high milestone to achieve. Even java generics are turing complete (https://arxiv.org/abs/1605.05274)