Scala的类型系统的哪个属性使图灵完成？

Question

Scala使用基于SystemFω的类型系统,通常认为它是强正规化的.强烈归一化意味着非图灵完整性.

然而,Scala的类型系统是Turing-complete.

与正式算法和系统相比,哪些更改/添加/修改使Scala的类型系统图灵完整？

Answer 1

这不是一个全面的答案，但原因是您可以定义递归类型。

我之前问过类似的问题（关于非图灵完整语言可能是什么样子）。答案的形式是：图灵完备的语言必须支持任意循环或递归。Scala 的类型系统支持后者

递归类型存在于大多数语言中，包括 Java 和 Pascal。任何引用自身的类型（如链表）都是递归的。您需要一种在类型级别执行计算的方法，例如类型应用程序。在 Scala 中，类型别名中有类型成员和部分类型应用。 (3认同)
我的意思是peano编码意义上的递归类型：http://apocalisp.wordpress.com/2010/06/08/type-level-programming-in-scala/ 使用“type”，而不是“class”或“trait” `。我认为考虑到上下文，这是相当明显的。就像我说的，我在这里呼应我所听到的有关图灵完备性的内容。 (2认同)