LINQ表达式树Turing是否完整？

Question

因为他们在.net 3.5。我知道他们在4.0，因为这是DLR的工作原理，但我对现在的版本很感兴趣。

Answer 1

LINQ表达式树可以表示任何可以放入普通C＃表达式的东西。因此，它们不能用来直接表示while循环，for循环等

然而，这是理论上可以使用lambda表达式和递归执行可能需要的任何迭代。在实践中，将Enumerable方法放入树中可能会更容易。

Answer 2

没有定义执行树的东西，我们不知道。在CLR自己的解释中（当你将它们编译成代表时）是这样的。但是，如果你将它们翻译成SQL，那么它们不是，你可以用你喜欢的任何属性来发明你自己的混淆解释。

在你决定如何解释它们之前，它们只是数据结构。

Answer 3

那么，你为什么不试图证明它呢？我敢打赌，这是一个有趣的挑战;）

但表达式树只代表一个表达式，因此你必须定义你允许做什么，如Earwicker所述。

如果允许表达式树使用递归，则可以实现重复，即循环等。

但是，无类型的lambda微积分是图灵完全的Turing_completeness＃示例，但Lambda微积分不允许递归本身Lambda_calculus＃递归它都是非常冒险的。

我会得出结论表达可能是图灵完成，但它会需要一个更熟悉这个来确认它的人。

Answer 4

在C＃3.0规范有在表达式树的部分提到保证金注释的早期草案：

我有图灵完备的真正奇妙的证明此幅度过遏制。

可悲的是，没有人能够找出谁写的或发展证明。