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.

Asphyxiate

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.

Urey

Hopefully it won't take 358 years. *8') – Remediable

They should've used version control and/or a Wiki :-p – Iwo

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.

Grantgranta

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.

Wellbred

LINQ expression trees do not support recursion so your only option seems to be to resort to boxing and a y-combinator, which will be very slow (an allocation per function call). – Frozen

Answer 4

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.

Snicker

You don't have to "allow" trees to use recursion - they already can be: blogs.msdn.com/madst/archive/2007/05/11/… – Myxomycete