Portal de Periódicos da CAPES

Java generics are turing complete

2017; Association for Computing Machinery; Volume: 52; Issue: 1 Linguagem: Inglês

10.1145/3093333.3009871

1558-1160

Radu Grigore,

Logic, Reasoning, and Knowledge

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.