“Java Generics Are Turing Complete”, 2016-05-17 (; backlinks):
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 2007.
It also follows that Java’s type checker can recognize any recursive language, which improves a result of 2016. The latter point is illustrated by a parser generator for fluent interfaces.
View PDF: