“"...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
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 条,统计用全部提及“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?)”
“> 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…”
- Python Type Hints Are Turing Complete ↗belter · 2022-09-03 · 1 分
- Python Type Hints Are Turing Complete ↗po · 2022-09-06 · 2 分
- Python type hints are Turing complete ↗nemoniac · 2022-09-09 · 246 分