In Java, generics refers to the implementation of parametric polymorphism. Introduced in Java 1.5 in 2004, generics enable making classes of containers parameterized in an arbitrary Java type, e.g. List<A> or Set<A>.
Java generics were initially specified carefully, but informally.
Early theoretical models of how they worked were more liberal than the actual implementation, and their subtype relation was undecidable [Kennedy and Pierce 2007]. In its appendix, the paper by Kennedy and Pierce contains a number of interesting Java programs that made Java 1.5 crash.
In a paper at POPL 2017, Grigore confirmed that subtype checking for Java generics is indeed undecidable. In fact, the paper shows that Java's type checker can recognise any recursive language [Grigore 2017].
Kennedy, Andrew J, and Benjamin C Pierce. ‘On Decidability of Nominal Subtyping with Variance’. In International Workshop on Foundations and Developments of Object-Oriented Languages (FOOL/WOOD), 2007. https://www.cis.upenn.edu/~bcpierce/papers/variance.pdf.
@inproceedings{kennedy_2007,
title = {On Decidability of Nominal Subtyping with Variance},
url = {https://www.cis.upenn.edu/~bcpierce/papers/variance.pdf},
booktitle = {International Workshop on Foundations and Developments of Object-Oriented Languages ({FOOL}/{WOOD})},
author = {Kennedy, Andrew J and Pierce, Benjamin C},
date = {2007}
}
Grigore, Radu. ‘Java Generics Are Turing Complete’. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, 73–85. Association for Computing Machinery, 2017. https://doi.org/10.1145/3009837.3009871.
@inproceedings{grigore_2017,
title = {Java generics are Turing complete},
doi = {10.1145/3009837.3009871},
pages = {73--85},
booktitle = {Proceedings of the 44th {ACM} {SIGPLAN} Symposium on Principles of Programming Languages},
publisher = {Association for Computing Machinery},
author = {Grigore, Radu},
date = {2017}
}