Czy drzewa wyrażenia LINQ Turing complete?

Question

Ponieważ są one w .Net 3.5. Wiem, że są w wersji 4.0, ponieważ to jest to, z czym pracuje DLR, ale interesuje mnie wersja, którą mamy teraz.

Answer 1

wyrażenie LINQ drzewa mogą reprezentować wszystko można umieścić w normalnym C# wypowiedzi. Jako takie, nie mogą być wykorzystane do bezpośredniego reprezentowania while pętle, for pętle itd

Jednakże, jest to teoretycznie możliwe, aby używać wyrażeń lambda i rekursji do przeprowadzenia jakiejkolwiek iteracji mogą być potrzebne. W praktyce może być łatwiej upuścić metody Enumerable do drzewa.

Answer 2

Bez zdefiniowania rzeczą, która wykona drzewa, nie wiemy. W samej interpretacji CLR (podczas kompilowania ich na delegatów) są oni. Ale jeśli przetłumaczysz je na SQL, to nie są, i możesz wymyślić własną, mylącą interpretację ich z dowolnymi właściwościami, które lubisz.

Dopóki nie zdecydowałeś, jak je interpretować, są one po prostu struktur danych.

Answer 3

Cóż, dlaczego nie spróbujesz to udowodnić? Założę się, że jest to zabawne wyzwanie;)

Ale drzewa wyrażeń reprezentują tylko wyrażenie i jako takie musisz zdefiniować, co możesz zrobić, jak stwierdził Earwicker.

Jeśli pozwolisz drzewa wyrażenie użyć rekurencji można osiągnąć powtórzenia czyli pętle i takie.

Jednak nie pomnożony rachunek lambda to Turing-complete Turing_completeness # Examples ale Lambda calculus nie zezwala na rekursję per se Lambda_calculus # Rekursja jest bardzo ryzykowna.

chciałbym stwierdzić, że ekspresja prawdopodobnie Turinga kompletne, ale będzie to wymagało kogoś, kto jest bardziej zaznajomieni z tym, aby je potwierdzić.

Answer 4

We wczesnym projekcie C# 3.0 specyfikacji znajdował się komentarz na marginesie sekcji na drzewach ekspresyjnych, że powiedział:

mam fenomenalnym dowód Turinga-zupełności których ten margines jest zbyt wąskie do zawarcia.

Niestety, nikt nie był w stanie dowiedzieć się, kto to napisał lub opracować dowód.