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

Python Type Hints are Turing Complete

Ori Roth · 2022
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 5 人首次 2022-09-03 · 最近 2023-09-18
5不同的人
2活跃月份
4讨论串
1被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Grigore showed that Java generics are Turing complete by describing a reduction from Turing machines to Java subtyping. We apply Grigore's algorithm to Python type hints and deduce that they are Turing complete. In addition, we present an alternative reduction in which the Turing machines are simulated in real time, resulting in significantly lower compilation times. Our work is accompanied by a Python implementation of both reductions that compiles Turing machines into Python subtyping machines.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论belter · 2022-09

“"...We apply Grigore’s algorithm to Python type hints and deduce that they are Turing complete. In addition, we present an alternative reduction in which the Turing machines are simulated in real time, resulting in significantly lower compilation times..." [PDF] - https://arxiv.org/pdf/2208.14755.pdf "OriRoth/python-typing-machines: Python Typing Machin…”

Python Type Hints Are Turing Complete原评论 ↗
评论w-m · 2022-09

“Here's the article rendered as html: https://ar5iv.labs.arxiv.org/html/2208.14755 (Replace the x in arxiv.org with a 5 to get there. I feel like it's working well enough in most cases, when will they start linking these from the actual arxiv article pages?)”

Python type hints are Turing complete原评论 ↗
评论bhouston · 2023-09

“> Rust’s type system ended up being Turing-complete anyway. It seems like it fell into the same trap as C++ templates: it’s an accidental programming language in a programming language, but with way worse syntax. Most anything in software can easily end up Turing-complete though. It isn't that high of a bar unfortunately. I think most mature type and tem…”

When Zig Outshines Rust – Memory Efficient Enum Arrays原评论 ↗
被提交为 story · 3 次