.net - LINQ式ツリーチューリングは完了していますか？

Question

.Net3.5にあるように。DLRが動作する4.0であることがわかっていますが、現在のバージョンに興味があります。

score 21 · Accepted Answer

C# 3.0 仕様の初期のドラフトでは、式ツリーに関するセクションの余白に次のようなコメントがありました。

私は、このマージンが狭すぎて含めることができないチューリング完全性の真に驚くべき証拠を持っています。

悲しいことに、誰がそれを書いたのか、あるいは証明を展開することができた人は誰もいません。

score 4 · Accepted Answer

ツリーを実行するものを定義しなければ、わかりません。CLR 独自の解釈 (デリゲートにコンパイルするとき) では、それらはそうです。しかし、それらを SQL に変換すると、そうではなく、好きなプロパティを使用して、独自の紛らわしい解釈を発明できます。

それらを解釈する方法を決定するまで、それらは単なるデータ構造です。

score 2 · Accepted Answer

LINQ 式ツリーは、通常の C# 式に入れることができるものなら何でも表すことができます。whileそのため、ループやforループなどを直接表すために使用することはできません。

ただし、ラムダ式と再帰を使用して、必要な反復を実行することは理論的には可能です。実際には、Enumerableメソッドをツリーにドロップする方が簡単な場合があります。

score 1 · Accepted Answer

では、それを証明しようとしないのはなぜですか。楽しいチャレンジだと思います ;)

しかし、式ツリーは式を表すだけなので、Earwicker が述べているように、実行できることを定義する必要があります。

式ツリーに再帰の使用を許可すると、繰り返し、つまり for ループなどを実現できます。

ただし、型なしラムダ計算はチューリング完全である Turing_completeness#Examples ですが、ラムダ計算では再帰自体は許可されません Lambda_calculus#Recursion すべてが非常に危険です。

式はおそらくチューリング完全であると結論付けますが、これを確認するには、これに詳しい人が必要です。

4 に答える 4