Skip to main content

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 (348kB) Preview
[thumbnail of javats.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL
https://dx.doi.org/10.1145/3009837.3009871

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
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: 10 Mar 2021 17:13 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/58183 (The current URI for this page, for reference purposes)
Grigore, Radu: https://orcid.org/0000-0003-1128-0311
  • Depositors only (login required):

Downloads

Downloads per month over past year