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)

PDF Author's Accepted Manuscript Language: English
Download this file (PDF/465kB)	Preview
Request a format suitable for use with assistive technology e.g. a screenreader
Official URL: https://dx.doi.org/10.1145/3009837.3009871
Additional URLs: Organisation

Abstract

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
Institutional Unit:	Schools > School of Computing
Former Institutional Unit:	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:	20 May 2025 10:19 UTC
Resource URI:	https://kar.kent.ac.uk/id/eprint/58183 (The current URI for this page, for reference purposes)

University of Kent Author Information

Grigore, Radu.

Creator's ORCID:	https://orcid.org/0000-0003-1128-0311
CReDIT Contributor Roles:

Depositors only (login required):

Altmetric

Total Views

Total unique views of this page since July 2020. For more details click on the image.