Java Generics are Turing Complete

Grigore, Radu (2017) Java Generics are Turing Complete. In: POPL 2017: Symposium on Principles of Programming Languages, 18 - 20 Jan 2017, Paris, France. (doi: (Full text available)

PDF - Author's Accepted Manuscript
Download (348kB) Preview
Official URL


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.

Item Type: Conference or workshop item (Paper)
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, > QA76.76 Computer software
Divisions: Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Radu Grigore
Date Deposited: 28 Oct 2016 11:29 UTC
Last Modified: 23 Jan 2017 15:48 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year