“Java's generic types are also Turing complete[0], and it hasn't been problematic.”
Java Generics are Turing Complete
把停机问题归约到 Java 子类型检查,证明其不可判定
论文给出从图灵机停机问题到 Java 子类型检查的归约,由此得出 Java 的子类型检查不可判定,回答了 Kennedy 和 Pierce 在 2007 年提出的问题。同时说明 Java 的类型检查器可以识别任何递归语言,改进了 Gil 与 Levy 2016 年的结果,并用一个面向流式接口(fluent interface)的解析器生成器来演示这一点。
评论者把它作为“Java 的类型系统本身图灵完备、子类型检查不可判定”的出处引用,常与 Rust、Haskell、Scala、TypeScript 等同样图灵完备的类型系统并列。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“So is Java's type system [1], and Rust's and Haskell's with some modest extensions, and Scala's.”
“A related result is that java generics are Turing complete [1].”
“anyone has written a useful program in them yet: Java Generics are Turing Complete”
“Java Generics are Turing complete. [1] You can produce an entire program inside a Java API.”
“Someone proved this and used the result to build a parser generator for fluent interfaces.”
看全部 10 条 →
“Java, C# ([LINK]), Scala ([LINK]), Haskell, Rust ([LINK]), Typescript ([LINK])”
“Incidentally, this issue also affects Java, which is both unsound [2] and undecidable [3].”
“Java generics are Turing complete: Java Generics are Turing Complete”
“it took until 2016 until it was finally proven that to be turing complete.”
- Java Generics Are Turing Complete ↗ingve · 2016-05-26 · 112 分
- Java generics are turing complete ↗ychen306 · 2017-12-17 · 3 分
- Java Generic Are Turing Complete ↗signa11 · 2018-02-14 · 3 分