C# 4.0是否在编译时是图灵完备的？

Question

众所周知，C++模板是图灵完备的, CSS也是图灵完备的 (!)，而C#重载决策是NP难问题（即使没有泛型）。

但是，C# 4.0（带有协变/逆变、泛型等）是否是编译时图灵完备呢？

- wizzard0

Answer 1

与C++中的模板不同，C#（以及其他.net语言）中的泛型是在运行时生成的特性。编译器会进行一些检查以验证类型的使用，但实际的替换发生在运行时。如果我没记错的话，协变和逆变也是如此。甚至预处理指令也是如此。有很多CLR的魔法。

（在实现层面上，主要区别在于C#泛型类型替换是在运行时执行的，因此泛型类型信息被保留为实例化对象）

请参阅MSDN。

http://msdn.microsoft.com/en-us/library/c6cyy67b(v=vs.110).aspx

更新： CLR 通过与编程集关联的元数据执行类型检查（参见Vis-à-vis Jit Compliation），它作为其众多服务之一进行此操作（其他包括内存管理和异常处理）。因此，我推断编译器对状态的理解既可以是进展的状态，也可以是机器内部状态（TC在部分上意味着能够有条件地回顾数据（符号）并评估先前数据（符号）的参考）。 （我犹豫不决地陈述TC的确切定义，因为我自己不确定是否完全掌握了它，因此请随时填写空白并在适用时纠正我。）因此，我会带着一点不安的心情说，是的，它可以。

- Terrance

---

泛型在运行时实例化，你是对的。但是“某些检查”也可能是图灵完备的。你永远不知道 :) 此外，预处理器指令是编译时的。 - wizzard0

预处理指令是编译时的，您说得对。我的错误，请让我修正。 - Terrance

但你说C#没有预处理器。我提到编译器有，并对此进行了更正。我在重复什么？此外，OP特别询问编译器是否是在添加了.NET运行时的其他功能后使用的TC。虽然我认为这不是一个完整的答案，但我认为它至少部分地解决了OP关于编译器的疑惑。 - Terrance

嗯，在更新答案后，如果我们将JIT视为C#编译器的一部分，则它绝对是图灵完备的。虽然它并不是:) 但是你让我思考了编译的TypeRef解析步骤，我认为我可以在其中编码一个图灵机。所以，我想现在我会接受这个答案并尝试 :) - wizzard0

有什么最新进展吗？这个话题在评论讨论的聊天中被提出，我很好奇。（显然，泛型是在运行时实例化的，但您能够将任意图灵机编码为运行时泛型实例化吗？） - Stephen Lin