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

Question

Как они есть в .Net 3.5. Я знаю, что они в 4.0, так как это то, с чем работает DLR, но меня интересует версия, которую мы сейчас имеем.

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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