Are LINQ expression trees Turing complete?

Question

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.

Answer 1

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:

I have a truly marvellous proof of Turing-completeness which this margin is too narrow to contain.

Sadly no one has been able to find out who wrote it or develop the proof.

Answer 2

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.

Answer 3

LINQ expression trees can represent anything you can put in a normal C# expression. As such, they can't be used to directly represent while loops, for loops, 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 Enumerable methods into your tree.