4
[2208.14755] Python Type Hints are Turing Complete
source link: https://arxiv.org/abs/2208.14755
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 31 Aug 2022]
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK