HackerPapers

arXiv:2208.14755cs.PL

Python Type Hints are Turing Complete

Ori Roth

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.PLProgramming Languages

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 4 threads, from Sep 2022 to Sep 2023. Found in 3 HN submissions from Sep 2022 to Sep 2022. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments4 threads

  1. Memory-efficient enum arrays in Zig 1 comment

    • > 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…

      bhoustonView on HNParent context

  2. Switching from C++ to Rust 1 comment

    • > 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)

      aw1621107View on HNParent context

  3. Python type hints are Turing complete 1 comment

    • 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?)

      w-mView on HNParent context

  4. Python Type Hints Are Turing Complete 1 comment

    • "...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]…

      belterView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.