8

Y コンビネータに関するウィキペディアの記事では、Y コンビネータの次の JavaScript 実装が提供されています。

function Y(f) {
    return (
        (function (x) {
            return f(function (v) { return x(x)(v); }); })
        (function (x) {
            return f(function (v) { return x(x)(v); }); })
    );
}

JavaScript に Y コンビネータが存在することは、すべての JavaScript 関数が不動点を持つことを意味するはずです ( for every function g, Y(g)andg(Y(g))は等しい必要があるため)。

ただし、違反する不動点のない関数を考え出すことは難しくありませんY(g) = g(Y(g))(こちらを参照)。特定の汎関数でさえ不動点を持たない (こちらを参照)。

すべての関数が不動点を持つという証明は、与えられた反例とどのように調和しますか? Y(g) = g(Y(g))JavaScript は、証明が適用される型指定されていないラムダ計算ではありませんか?

4

3 に答える 3

4

私がウィキペディアの記事を理解している限り、「すべての JavaScript 関数に固定点がある」ということをどこにも暗示しているわけではありません。

いいえ、その記事の定義と固定小数点に関する記事によると、JavaScript は型指定されていないラムダ計算にすることはできませfunction f(x){ return x + 1 }んx ^ 1。 -numbers であるため、「すべての関数に少なくとも 1 つの固定小数点がある」チェックも失敗します。

于 2012-06-14T14:50:48.460 に答える
3

不動点理論にはいくつかの特徴があります。プログラミング言語に関するものは、表示意味論の見出しの下で研究されます。それらは、特別なプロパティを持つ構造化された可算セットを形成する値に依存します。 格子と完全部分順序は 2 つの例です。これらのセットにはすべて「底」要素があり、これは「有用な結果がない」ことを意味する固定点であることが判明しました。実際、コンピューター プログラムで関心のある不動点演算子は、最も小さいものだけです。固定小数点演算子: 構造化された値のセットで最も低い固有の最小固定小数点を見つける演算子。(これらの構造化されたセットでは、すべての整数が同じ「レベル」にあることに注意してください。その下にあるのは一番下の要素だけです。残りの層は、関数やタプル型などのより複雑な型、つまり構造体で構成されています。) 、これはそれをかなりうまくレイアウトします。タルスキーの不動点定理は、単調な(または交互に連続的な) すべての関数が不動点を持つことを実際に示しています。定義については、上記のリファレンスを参照してください。操作可能なコンピューター プログラムでは、一番下の要素は非終了計算、つまり無限再帰に対応します。

これらすべての要点は、計算の厳密な数学的モデルがあれば、型システムとプログラムの正しさについて興味深いことを証明し始めることができるということです。したがって、それは単なる学術的な演習ではありません。

于 2012-06-22T04:09:08.670 に答える