Полны ли деревья выражений LINQ по Тьюрингу?

Деревья выражений LINQ могут представлять все, что вы можете вставить в обычное выражение C#. Таким образом, они не могут использоваться для прямого представления петель while, петель for и т. д.

Однако теоретически можно использовать лямбда-выражения и рекурсию для выполнения любой итерации, которая может вам понадобиться. На практике может быть проще добавить методы Enumerable в ваше дерево.

Без определения того, что будет выполнять дерево, мы не знаем. В собственной интерпретации CLR (когда вы компилируете их в делегатов) да. Но если вы переведете их в SQL, это не так, и вы можете придумать свою собственную сбивающую с толку их интерпретацию с любыми свойствами, которые вам нравятся.

Пока вы не решите, как их интерпретировать, это просто структуры данных.

А почему бы тебе не попробовать это доказать? Бьюсь об заклад, это забавный вызов;)

Но деревья выражений представляют собой только выражение, и поэтому вам нужно будет определить, что вам разрешено делать, как заявил Эрвикер.

Если вы разрешите деревьям выражений использовать рекурсию, вы можете добиться повторения, то есть для циклов и т. д.

Однако нетипизированное лямбда-исчисление является полным по Тьюрингу Turing_completeness # Примеры, но лямбда-исчисление не допускает рекурсию как таковую Lambda_calculus # Рекурсия - это все очень рискованно.

Я бы пришел к выводу, что это выражение, вероятно, завершено по Тьюрингу, но для его подтверждения потребуется кто-то, кто более знаком с этим.

В раннем черновике спецификации C# 3.0 на полях раздела о деревьях выражений был комментарий, в котором говорилось:

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

К сожалению, никому не удалось выяснить, кто это написал, или разработать доказательство.