论文标题
Python型提示已完成
Python Type Hints are Turing Complete
论文作者
论文摘要
格里戈尔（Grigore）表明，Java Generics通过描述从图灵机到Java子类型的减少来完成Turing。我们将Grigore的算法应用于Python型提示，并推断出它们已经完成。此外，我们提出了一种替代性降低，其中图灵机是实时模拟的，导致汇编时间明显降低。我们的工作伴随着两种减少的实施，将图灵机汇编成Python子类型机器。
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.
