Skip to main content
Kent Academic Repository

Java Generics are Turing Complete

Grigore, Radu (2017) Java Generics are Turing Complete. In: POPL 2017 Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. POPL Principles of Programming Languages . pp. 73-85. ACM, New York, USA ISBN 978-1-4503-4660-3. (doi:10.1145/3009837.3009871) (KAR id:58183)


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 Gill and Levy from 2016. The latter point is illustrated by a parser generator for fluent interfaces.

Item Type: Conference or workshop item (Paper)
DOI/Identification number: 10.1145/3009837.3009871
Uncontrolled keywords: Java, subtype checking, decidability, fluent interface, parser generator, Turing machine
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, > QA76.76 Computer software
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Radu Grigore
Date Deposited: 28 Oct 2016 11:29 UTC
Last Modified: 04 Mar 2024 16:44 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.