arXiv:1605.05274cs.PL
This paper describes a reduction from the halting problem of Turing machines to subtype checking in Java. It follows that subtype checking in Java is undecidable, which answers a question posed by Kennedy and Pierce in 2007. It also follows that Java's type checker can recognize any recursive language, which improves a result of Gil and Levy from 2016. The latter point is illustrated by a parser generator for fluent interfaces.
Linked by 18 identifiable commenters in 19 comments across 15 threads, from May 2016 to Sep 2023. Found in 3 HN submissions from May 2016 to Feb 2018. Open submission discussions.
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…
> 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)…
Java's type system is also turing complete: 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#…
> 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)
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
I haven’t understand the details, but supposedly Java generics are also Turing complete: https://arxiv.org/pdf/1605.05274.pdf
Java Generics are Turing complete. [1] You can produce an entire program inside a Java API. The API is part of the implementation in Java. The criteria for copyright is originality and creativity. [2] It doesn't matter if understanding hashcodes is hard. Mathematical functions…
https://arxiv.org/abs/1605.05274 perhaps?
Theoretically, sure: 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
I think it's a good idea to link to abstracts https://arxiv.org/abs/1605.05274 (as ygra does (https://news.ycombinator.com/item?id=19777896 )) rather than directly to PDFs.
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…
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…
In related news: Radu Grigore "Java generics are Turing complete" POPL'17 Preprint: https://arxiv.org/pdf/1605.05274
http://arxiv.org/pdf/1605.05274v1.pdf in the upper right corner of the page
Connected through shared HN threads, not inferred similarity or a recommendation.
> 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…
bhoustonView on HNParent context
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…
ynikView on HNParent context