Y Combinator: कुछ कार्य नियत बिन्दु

Question

नहीं है Wikipedia article on the Y combinator Y Combinator के निम्नलिखित जावास्क्रिप्ट कार्यान्वयन प्रदान करता है:

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

जावास्क्रिप्ट में एक Y Combinator के अस्तित्व का मतलब यह चाहिए कि हर JavaScript फ़ंक्शन एक नियत बिन्दु है (चूंकि प्रत्येक फ़ंक्शन g, Y(g) और g(Y(g)) बराबर होना चाहिए)।

हालांकि, Y(g) = g(Y(g)) का उल्लंघन करने वाले फिक्स्ड पॉइंट्स के बिना फ़ंक्शंस के साथ आना मुश्किल नहीं है (here देखें)। यहां तक ​​कि कुछ फ़ंक्शंस में निश्चित बिंदु नहीं होते हैं (here देखें)।

सबूत कैसे है कि प्रत्येक कार्य में एक निश्चित बिंदु है जो दिए गए काउंटर-उदाहरणों के साथ मेल खाता है? क्या जावास्क्रिप्ट एक untyped lambda कैलकुलस नहीं है जिसमें सबूत है कि Y(g) = g(Y(g)) लागू होता है?

Answer 1

लैम्ब्डा अभिव्यक्तियों की समस्या यह है कि उन्हें गणितीय अर्थ में कार्यों के रूप में व्याख्या नहीं किया जा सकता है, यानी एक सेट से दूसरे में मैपिंग।

कारण पर ही एक सेट A से कार्यों का सेट की प्रमुखता है हमेशा A की प्रमुखता से बड़ा है, इसलिए नहीं AA करने से सभी कार्यों A का एक तत्व हो सकता है। यही है, एक समारोह f: A -> A है जिसके लिए अभिव्यक्ति f(f) समझ में नहीं आता है।

यह "सभी सेटों का सेट स्वयं नहीं है" जैसा है, जो तार्किक रूप से समझ में नहीं आता है।

जावास्क्रिप्ट लैम्ब्डा कैलकुस का मॉडल नहीं है।

अपने उदाहरण के साथ समस्या यह है कि

(lambda x.g(x x)) (lambda x.g(x x)) 

g((lambda x.g(x x)) (lambda x.g(x x))) 

के बराबर होना चाहिए, लेकिन यह आपकी जावास्क्रिप्ट कार्यक्रम है जहाँ g0 का सूचक समारोह है में नहीं है।

x x हमेशा undefined है। इसलिए पहली पंक्ति g (undefined) = 0 का मूल्यांकन करती है। दूसरी पंक्ति g (g (undefined)) = g (0) = 1 का मूल्यांकन करती है। इसका मतलब है कि लैम्ब्डा कैलकुस का आपका जावास्क्रिप्ट मॉडल वास्तव में एक मॉडल नहीं है।

प्रत्येक गैर खाली सेट D एक नियत बिन्दु के बिना D करने के लिए D से एक समारोह है वहाँ के लिए के बाद से, स्पष्ट रूप से वहाँ लैम्ब्डा पथरी का कोई मॉडल हो सकता है। मुझे लगता है कि यह साबित करना भी संभव होना चाहिए कि किसी भी ट्यूरिंग-पूर्ण भाषा में वाई-संयोजक का कार्यान्वयन नहीं किया जा सकता है।

Answer 2

जहां तक ​​मैं विकिपीडिया लेख को समझता हूं, यह कहीं भी यह नहीं दर्शाता है कि "प्रत्येक जावास्क्रिप्ट फ़ंक्शन का एक निश्चित बिंदु होता है" और यह उदाहरण केवल यह दिखाता है कि वाई विनिर्देशक को उनके विनिर्देशों के अनुसार कार्यान्वित करने के लिए कैसे लागू किया जाए।

और नहीं, उस लेख और an article on fixed point में परिभाषाओं के अनुसार, जावास्क्रिप्ट नहीं एक untyped लैम्ब्डा पथरी हो सकता है, क्योंकि यह काम करता है कि स्पष्ट रूप से असफल जाँच "एक नियत बिन्दु है", function f(x){ return x + 1 } या x^1 की तरह तैयार कर सकते हैं यदि आप चाहते हैं गैर-संख्याएं शामिल करें और इस प्रकार विफल हो जाएं "प्रत्येक फ़ंक्शन में कम से कम एक निश्चित बिंदु" चेक भी है।

Answer 3

फिक्स्ड पॉइंट सिद्धांत स्वादों में आता है। प्रोग्रामिंग भाषाओं के लिए उन लोगों का अध्ययन डायोडोटेशनल अर्थशास्त्र के शीर्षक के तहत किया जाता है। वे विशेष गुणों के साथ एक संरचित गणनीय सेट बनाने वाले मूल्यों पर निर्भर करते हैं। Lattices और Complete Partial Orders दो उदाहरण हैं। इन सभी सेटों में "नीचे" तत्व होता है, जो निश्चित बिंदु बन जाता है जिसका अर्थ है "कोई उपयोगी परिणाम नहीं"। वास्तव में, कंप्यूटर प्रोग्राम्स के साथ आप रुचि रखने वाले एकमात्र निश्चित बिंदु ऑपरेटर कम से कम फिक्स्ड पॉइंट ऑपरेटर हैं: जो अद्वितीय न्यूनतम निश्चित बिंदु पाते हैं जो मूल्यों के संरचित सेट में सबसे कम है। (ध्यान दें कि सभी पूर्णांक इन संरचित सेटों में एक ही "स्तर" पर हैं। केवल नीचे तत्व नीचे रहता है। शेष परतें अधिक जटिल प्रकारों से बना होती हैं जैसे फ़ंक्शन और ट्यूपल प्रकार, यानी संरचनाएं।) यदि आपके पास कुछ अलग गणित है , this इसे बहुत अच्छी तरह से प्रस्तुत करता है। तर्स्की का निश्चित बिंदु प्रमेय वास्तव में कहता है कि प्रत्येक कार्य मोनोटोन (या वैकल्पिक रूप से निरंतर) का एक निश्चित बिंदु है। परिभाषाओं के लिए उपर्युक्त संदर्भ देखें। परिचालन कंप्यूटर प्रोग्राम में, निचला तत्व एक गैर-समाप्ति गणना के अनुरूप है: एक अनंत रिकर्सन।

यह सब बात यह है कि यदि आपके पास गणना का कठोर गणितीय मॉडल है, तो आप टाइप सिस्टम और प्रोग्राम शुद्धता के बारे में दिलचस्प चीजों को साबित करना शुरू कर सकते हैं। तो यह सिर्फ एक अकादमिक अभ्यास नहीं है।