LINQ 表达式树图灵完备吗？
正如它们在 .Net 3.5 中一样。 我知道它们是 4.0 版本，因为 DLR 就使用该版本，但我对我们现在拥有的版本感兴趣。
As they are in .Net 3.5. I know they are in 4.0, as that's what the DLR works with, but I'm interested in the version we have now.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
在 C# 3.0 规范的早期草案中，表达式树部分的页边空白处有一条评论：
遗憾的是，没有人能够查出是谁写的，也没有人能够证明这一点。
In the early draft of the C# 3.0 spec there was a comment in the margin of the section on expression trees that said:
Sadly no one has been able to find out who wrote it or develop the proof.
如果不定义将执行树的东西，我们就不知道。 在 CLR 自己的解释中（当您将它们编译为委托时）它们是。 但如果你将它们翻译成 SQL，它们就不是，你可以用你喜欢的任何属性发明你自己的令人困惑的解释。
在您决定如何解释它们之前，它们只是数据结构。
Without defining the thing that will execute the tree, we don't know. In the CLR's own interpretation (when you compile them into delegates) they are. But if you translate them into SQL, they are not, and you can invent your own confusing interpretation of them with whatever properties you like.
Until you've decided how to interpret them, they're just data structures.
LINQ 表达式树可以表示可以放入普通 C# 表达式中的任何内容。 因此，它们不能用于直接表示
while循环、for循环等。但是，理论上可以使用 lambda 表达式和递归来执行任何迭代你可能需要。 实际上，将
Enumerable方法放入树中可能会更容易。LINQ expression trees can represent anything you can put in a normal C# expression. As such, they can't be used to directly represent
whileloops,forloops, etc.However, it's theoretically possible to use lambda expressions and recursion to carry out any iteration you may need. In practice it may be easier to drop
Enumerablemethods into your tree.好吧，你为什么不尝试证明一下呢？ 我打赌这是一个有趣的挑战;)
但是表达式树仅代表一个表达式，因此您必须定义您可以做什么，如 Earwicker 所说。
如果允许表达式树使用递归，您可以实现重复，即 for 循环等。
然而，无类型 lambda 演算是图灵完备的 Turing_completeness#Examples 但 Lambda 演算本身不允许递归 Lambda_calculus#Recursion 这一切都非常危险。
我的结论是，表达式可能是图灵完备的，但需要更熟悉这一点的人来证实它。
Well, why don't you try to prove it? I bet it's a fun challenge ;)
But expression trees only represent an expression and as such you'll have to define what you are allowed to do, as stated by Earwicker.
If you allow expression trees to use recursion you can achieve repetition i.e. for loops and such.
However, untyped lambda calculus is Turing-complete Turing_completeness#Examples but Lambda calculus does not permit recursion per se Lambda_calculus#Recursion it's all very dicey.
I would conclude that expression are probably Turing complete but it will require someone who is more familiar with this to confirm it.