按年被提到
20162017 · 3 次2026
编程语言与编译器›类型系统与函数式语言·arXiv:1605.05274 · cs.PL

Java Generics are Turing Complete

Java 泛型是图灵完备的
Radu Grigore · 2016

把停机问题归约到 Java 子类型检查,证明其不可判定

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 13 人首次 2016-05-26 · 最近 2023-09-18
13不同的人
12活跃月份
12讨论串
9被引(OpenAlex)

论文给出从图灵机停机问题到 Java 子类型检查的归约,由此得出 Java 的子类型检查不可判定,回答了 Kennedy 和 Pierce 在 2007 年提出的问题。同时说明 Java 的类型检查器可以识别任何递归语言,改进了 Gil 与 Levy 2016 年的结果,并用一个面向流式接口(fluent interface)的解析器生成器来演示这一点。

HN 为什么提它

评论者把它作为“Java 的类型系统本身图灵完备、子类型检查不可判定”的出处引用,常与 Rust、Haskell、Scala、TypeScript 等同样图灵完备的类型系统并列。

其他难度 4 / 5约 40 分钟经得起时间
读之前最好知道
1图灵机与停机问题(halting problem)
2Java 泛型与子类型检查
3可判定性与递归语言
4类型系统基础

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用unholiness · 2017-08

“Java's generic types are also Turing complete[0], and it hasn't been problematic.”

以 Java 泛型图灵完备为例,说明这并未造成问题
TypeScripts Type System Is Turing Complete原评论 ↗
引用naasking · 2017-10

“So is Java's type system [1], and Rust's and Haskell's with some modest extensions, and Scala's.”

指出 Java 类型系统图灵完备,其他语言也类似
Classification of the principal programming paradigms原评论 ↗
引用Jaxan · 2018-05

“A related result is that java generics are Turing complete [1].”

补充相关结果:Java 泛型是图灵完备的
Formal Language Recognition with the Java Type Checker (2016) [pdf]原评论 ↗
引用saagarjha · 2019-04

“anyone has written a useful program in them yet: Java Generics are Turing Complete”

好奇是否有人用它写过有用的程序
How Many Type Parameters Can a Java Method Have?原评论 ↗
引用panny · 2019-06

“Java Generics are Turing complete. [1] You can produce an entire program inside a Java API.”

指出 Java 泛型图灵完备,可在 API 里写出整个程序
Google/Oracle’s $9B Copyright Case Could Be Headed for the Supreme Court原评论 ↗
引用doctor_n_ · 2020-05

“Someone proved this and used the result to build a parser generator for fluent interfaces.”

提到有人证明了这点,并据此做出流式接口的解析器生成器
Show HN: FizzBuzz purely in Rust's trait system原评论 ↗
看全部 10 条 →
引用jcelerier · 2021-07

“Java, C# ([LINK]), Scala ([LINK]), Haskell, Rust ([LINK]), Typescript ([LINK])”

列举各语言类型系统图灵完备,Java 以这篇为证
Compiling Rust is NP-hard原评论 ↗
引用bmc7505 · 2022-10

“Incidentally, this issue also affects Java, which is both unsound [2] and undecidable [3].”

指出 Java 类型系统既不健全又不可判定
From zero to 10M lines of Kotlin原评论 ↗
引用bhouston · 2023-09

“Java generics are Turing complete: Java Generics are Turing Complete”

把 Java 泛型图灵完备作为其中一个例子
When Zig Outshines Rust – Memory Efficient Enum Arrays原评论 ↗
引用ynik · 2023-09

“it took until 2016 until it was finally proven that to be turing complete.”

指出直到 2016 年才证明 Java 泛型图灵完备
When Zig Outshines Rust – Memory Efficient Enum Arrays原评论 ↗
被提交为 story · 3 次