なぜ価値のある評価戦略が完全にならないのですか？

Question

私は別の記事を読んでいます 評価戦略 （私はWikiの記事をリンクしましたが、英語ではない別の記事を読んでいます）。そして、それはとは異なります call-by-name と call-by-need 戦略、 call-by-value 戦略はです いいえ チューリング完全.

誰かが説明できますか、なぜそうなのですか？可能であれば、PLSの例を追加します。

Answer 1

私は主張に異議を唱えます あなたが読んでいる記事で。 （私はこれに対して報酬を受け取っていないので、証拠ではなく、示唆的な議論を提供するつもりです。）

少なくとも通常の注文の削減（別名、名前による呼び出し）の下では、純粋なラムダ微積分が完全に完全になっていることはよく知られています。しかし、ジョン・レイノルズの独創的な論文を見るなら 高次プログラミング言語の定義通訳, 、レイノルズが名前でコールとバリューの呼び出しの違いについて長々と議論していることがわかります。議論の重要な部分は、適切な区別をするために、プログラムをに変換できるということです。 継続パススタイル. 。 CPS変換は、ニーズによる呼び出しと値ごとの呼び出しに対して異なりますが、結果の変換された用語はどちらのスタイルでも評価できます。

したがって、ここに議論があります。チューリングマシンをシミュレートするLambda-Calculusプログラムを作成し、CBN変換を使用してCPS変換を行い、CBV削減戦略を使用して結果のコードを評価できます。強打！チューリングコンプリート。

実際には、チューリングマシンをエミュレートするCBVプログラムを作成できると思います。たとえば、θのように、適切な固定点コンビネーターを選択するのに十分です。 （より有名なYコンビネーターは、コールバイネーム削減戦略、すなわち、通常の注文削減の下でのみ機能します。）

免責事項： 私は年齢のラムダ計算を研究していませんが、上記の議論にはいくつかの詳細が間違っていると確信しています。しかし、私は物質に自信があります。プログラミング言語理論に関するオンラインリソースで露骨に間違ったものを見つけたのは初めてではありません。

Answer 2

あなたの質問は特定の言語に言及せずにあまり意味がありませんが、私は未投げのラムダ微積分に関して答えを最大限に活用します。

Untyped Lambda Calculusの呼び出しごとの固定点コンビネーター（すなわち "yコンビネーター"）の存在は、基本的な主張に反論しているようです（参照： 固定点コンビネーター）。このようなコンビネーターの存在は、強い正規化を破ります。これは、価値のある評価戦略を使用する完全なチューリングが完全にある言語が少なくとも1つあることを示唆しています。

言語のチューリングの完全性に影響を与える可能性がはるかに高いことは、タイプシステムの存在（または不足）です。たとえば、シンプルなラムダ計算は固定点コンビネーターをエンコードすることはできず、強く正常化しています（つまり、すべての十分なタイプの用語は値に減少します）が、これは採用されている評価戦略に関係なく真です。むしろ、タイプシステムの結果です。