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.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
> 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 template systems end up as Turing-complete. To single out Rust for this is to ignore that this is just standard fare for mature typing systems.
TypeScript's types are Turing complete: https://github.com/microsoft/TypeScript/issues/14833
Python's type hints are Turing complete: https://arxiv.org/abs/2208.14755
Java generics are Turing complete: https://arxiv.org/abs/1605.05274
> even though C++ has a significantly more complex type system (it's type system is TC)
For what it's worth, Python's type hints are also Turing complete (https://arxiv.org/abs/2208.14755, discussed on HN at https://news.ycombinator.com/item?id=32779296)
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?)
"...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 Machines 1.0" - https://zenodo.org/record/7004898
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.
Jon Kleinberg, Sendhil Mullainathan, Manish Raghavan
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups.