कम से कम निश्चित बिंदु

फलन f(x) = x² − 4 में दो निश्चित बिंदु हैं, जो नीली रेखा के साथ प्रतिच्छेदन के रूप में दिखाए गए हैं; इसका कम से कम एक 1/2 − पर है√17/2.

आदेश सिद्धांत में, गणित की एक शाखा, आंशिक रूप से सेट किए गए सेट से एक फ़ंक्शन (गणित) का कम से कम निश्चित बिंदु (एलएफपी या एलएफपी, कभी-कभी सबसे छोटा निश्चित बिंदु) निश्चित बिंदु (गणित) है जो एक दूसरे से कम है पोसेट के आदेश के अनुसार निश्चित बिंदु। एक फ़ंक्शन के लिए कम से कम निश्चित बिंदु होना आवश्यक नहीं है, लेकिन यदि ऐसा होता है तो कम से कम निश्चित बिंदु अद्वितीय होता है।

उदाहरण के लिए, वास्तविक संख्याओं पर सामान्य क्रम के साथ, वास्तविक फ़ंक्शन f(x) = x का न्यूनतम निश्चित बिंदु² x = 0 है (चूंकि केवल अन्य नियत बिंदु 1 और 0 < 1 है)। इसके विपरीत, f(x) = x + 1 का कोई निश्चित बिंदु नहीं है, इसलिए कम से कम एक नहीं है, और f(x) = x में अपरिमित रूप से कई निश्चित बिंदु हैं, लेकिन कम से कम एक नहीं है।

उदाहरण

होने देना $G=(V,A)$ एक निर्देशित ग्राफ बनें और $v$ एक शिखर हो। शीर्षों का समुच्चय (गणित) से पहुँचा जा सकता है $v$ फ़ंक्शन के कम से कम निश्चित बिंदु के रूप में परिभाषित किया जा सकता है $f:\wp (V)\to \wp (V)$ , के रूप में परिभाषित $f(X)=\{v\}\cup \{x\in V:{\text{ for some }}w\in X{\text{ there is an arc from }}w{\text{ to }}x\}.$ शीर्षों का सेट जो से सह-सुलभ हैं $v$ एक समान कम से कम फिक्स-पॉइंट द्वारा परिभाषित किया गया है। का दृढ़ता से जुड़ा हुआ घटक $v$ उन दो सबसे कम निश्चित बिंदुओं का प्रतिच्छेदन (सेट सिद्धांत) है।

होने देना $G=(V,\Sigma ,R,S_{0})$ एक संदर्भ-मुक्त व्याकरण बनें। सेट $E$ प्रतीकों का जो खाली स्ट्रिंग उत्पन्न करता है $\varepsilon$ फ़ंक्शन के कम से कम निश्चित बिंदु के रूप में प्राप्त किया जा सकता है $f:\wp (V)\to \wp (V)$ , के रूप में परिभाषित $f(X)=\{S\in V:\;S\in X{\text{ or }}(S\to \varepsilon )\in R{\text{ or }}(S\to S^{1}\dots S^{n})\in R{\text{ and }}S^{i}\in X{\text{, for all }}i\}$ , कहां $\wp (V)$ के पावर सेट को दर्शाता है $V$ .

अनुप्रयोग

कई निश्चित-बिंदु प्रमेय कम से कम निश्चित बिंदु का पता लगाने के लिए एल्गोरिदम उत्पन्न करते हैं। कम से कम निश्चित बिंदुओं में अक्सर वांछनीय गुण होते हैं जो मनमाना निश्चित बिंदु नहीं होते हैं।

सांकेतिक शब्दार्थ

आंशिक आदेश चालू

\mathbb {Z} _{\bot }

कंप्यूटर विज्ञान में, सांकेतिक शब्दार्थ दृष्टिकोण किसी दिए गए प्रोग्राम टेक्स्ट से संबंधित गणितीय फ़ंक्शन प्राप्त करने के लिए कम से कम निश्चित बिंदुओं का उपयोग करता है, जिसे शब्दार्थ कहा जाता है। इसके लिए, एक कृत्रिम गणितीय वस्तु, $\bot$ , असाधारण मूल्य अपरिभाषित को दर्शाते हुए पेश किया गया है।

दिया उदा. प्रोग्राम डेटाटाइप int, इसके गणितीय समकक्ष के रूप में परिभाषित किया गया है $\mathbb {Z} _{\bot }=\mathbb {Z} \cup \{\bot \};$ इसे परिभाषित करके आंशिक रूप से क्रमबद्ध सेट बनाया जाता है $\bot \sqsubset n$ प्रत्येक के लिए $n\in \mathbb {Z}$ और किन्हीं दो अलग-अलग सदस्यों को अनुमति देना $n,m\in \mathbb {Z}$ अतुलनीय w.r.t. $\sqsubset$ , तस्वीर देखो।

एक कार्यक्रम परिभाषा के शब्दार्थ int f(int n){...} कुछ गणितीय कार्य है $f:\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }.$ यदि कार्यक्रम की परिभाषा f कुछ इनपुट के लिए समाप्त नहीं होता है n, इसे गणितीय रूप में व्यक्त किया जा सकता है $f(n)=\bot .$ सभी गणितीय फलनों के समुच्चय को परिभाषित करके आंशिक रूप से क्रमित किया जाता है $f\sqsubseteq g$ अगर, प्रत्येक के लिए $n,$ रिश्ता $f(n)\sqsubseteq g(n)$ रखता है, यानी अगर $f(n)$ कम परिभाषित या बराबर है $g(n).$ उदाहरण के लिए, अभिव्यक्ति का शब्दार्थ x+x/x की तुलना में कम परिभाषित है x+1, पूर्व के बाद से, लेकिन बाद वाले नहीं, नक्शे $0$ को $\bot ,$ और वे अन्यथा सहमत हैं।

कुछ कार्यक्रम पाठ दिया f, इसके गणितीय समकक्ष को कार्यों से लेकर कार्यों तक कुछ मैपिंग के कम से कम निश्चित बिंदु के रूप में प्राप्त किया जाता है जिसे अनुवाद करके प्राप्त किया जा सकता है f. उदाहरण के लिए, सी (प्रोग्रामिंग भाषा) परिभाषा

int fact(int n) { if (n == 0) तो return 1; अन्यथा वापसी n * तथ्य (n-1); }

मानचित्रण में अनुवादित है

F:(\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot })\to (\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }),

के रूप में परिभाषित

(F(f))(n)={\begin{cases}1&{\text{if }}n=0,\\n\cdot f(n-1)&{\text{if }}n\neq \bot {\text{ and }}n\neq 0,\\\bot &{\text{if }}n=\bot .\\\end{cases}}

मानचित्रण

F

हालांकि, गैर-पुनरावर्ती तरीके से परिभाषित किया गया है fact पुनरावर्ती रूप से परिभाषित किया गया था।

कुछ प्रतिबंधों के तहत (देखें क्लेन फिक्स्ड-पॉइंट प्रमेय), जो उदाहरण में मिले हैं, $F$ आवश्यक रूप से कम से कम निश्चित बिंदु है, $\operatorname {fact}$ , वह है $(F(\operatorname {fact} ))(n)=\operatorname {fact} (n)$ सबके लिए $n\in \mathbb {Z} _{\bot }$ .^[1] यह दिखाना संभव है

\operatorname {fact} (n)={\begin{cases}n!&{\text{if }}n\geq 0,\\\bot &{\text{if }}n<0{\text{ or }}n=\bot .\end{cases}}

का एक बड़ा निश्चित बिंदु

F

उदा. कार्यक्रम

\operatorname {fact} _{0},

द्वारा परिभाषित

\operatorname {fact} _{0}(n)={\begin{cases}n!&{\text{if }}n\geq 0,\\0&{\text{if }}n<0,\\\bot &{\text{if }}n=\bot ,\end{cases}}

हालाँकि, यह फ़ंक्शन नकारात्मक के लिए उपरोक्त प्रोग्राम टेक्स्ट के व्यवहार को सही ढंग से नहीं दर्शाता है

n;

उदा. कॉल fact(-1) बिल्कुल भी समाप्त नहीं होगा, वापस जाने की तो बात ही छोड़ दें 0.

केवल सबसे कम निश्चित बिंदु, $\operatorname {fact} ,$ यथोचित रूप से गणितीय कार्यक्रम शब्दार्थ के रूप में उपयोग किया जा सकता है।

वर्णनात्मक जटिलता

नील इमरमैन^[2]^[3] और मोशे वाई. वर्दी^[4] स्वतंत्र रूप से वर्णनात्मक जटिलता का परिणाम दिखाया गया है कि पी (जटिलता) | रैखिक क्रम संरचनाओं के बहुपद-समय संगणनीय गुण एफओ (एलएफपी) में निश्चित हैं, यानी कम से कम निश्चित बिंदु ऑपरेटर के साथ पहले क्रम के तर्क में। हालांकि, एफओ (एलएफपी) अनियंत्रित संरचनाओं के सभी बहुपद-समय गुणों को व्यक्त करने के लिए बहुत कमजोर है (उदाहरण के लिए एक संरचना में समानता (गणित) आकार है)।

सबसे बड़ा निश्चित बिंदु

सबसे बड़े निश्चित बिंदु भी निर्धारित किए जा सकते हैं। वास्तविक संख्याओं के मामले में परिभाषा कम से कम निश्चित बिंदु के साथ सममित है, लेकिन कंप्यूटर विज्ञान में वे कम से कम निश्चित बिंदुओं से कम सामान्यतः उपयोग किए जाते हैं। विशेष रूप से, डोमेन सिद्धांत में पाए जाने वाले पॉसेट्स में आमतौर पर सबसे बड़ा तत्व नहीं होता है, इसलिए कई, परस्पर अतुलनीय अधिकतम तत्व निश्चित बिंदु हो सकते हैं, और सबसे बड़ा निश्चित बिंदु मौजूद नहीं हो सकता है। इस समस्या को हल करने के लिए, इष्टतम निश्चित बिंदु को अन्य सभी निश्चित बिंदुओं के साथ संगत सबसे परिभाषित निश्चित बिंदु के रूप में परिभाषित किया गया है। इष्टतम निश्चित बिंदु हमेशा मौजूद होता है, और सबसे बड़ा निश्चित बिंदु होता है यदि सबसे बड़ा निश्चित बिंदु मौजूद होता है। इष्टतम निश्चित बिंदु पुनरावर्ती और कोरकर्सिव कार्यों के औपचारिक अध्ययन की अनुमति देता है जो कम से कम निश्चित बिंदु के साथ अभिसरण नहीं करते हैं।^[5] दुर्भाग्य से एक प्रभावी पुनरावर्ती परिभाषा का इष्टतम निश्चित बिंदु एक गैर-गणना योग्य कार्य हो सकता है^[6] इसलिए यह मुख्य रूप से सैद्धांतिक हित का है।

यह भी देखें

कैम्स्टर-टार्स्की प्रमेय
फिक्स्ड-पॉइंट लॉजिक

↑ C.A. Gunter; D.S. Scott (1990). "Semantic Domains". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 633–674. ISBN 0-444-88074-7. Here: pp. 636–638
↑ N. Immerman, Relational queries computable in polynomial time, Information and Control 68 (1–3) (1986) 86–104.
↑ Immerman, Neil (1982). "Relational Queries Computable in Polynomial Time". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 147–152. doi:10.1145/800070.802187. Revised version in Information and Control, 68 (1986), 86–104.
↑ Vardi, Moshe Y. (1982). "The Complexity of Relational Query Languages". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 137–146. doi:10.1145/800070.802186.
↑ Charguéraud, Arthur (2010). "The Optimal Fixed Point Combinator" (PDF). Interactive Theorem Proving. 6172: 195–210. doi:10.1007/978-3-642-14052-5_15. Retrieved 30 October 2021.
↑ Shamir, Adi (October 1976). The fixedpoints of recursive definitions (Ph.D. thesis). Weizmann Institute of Science. OCLC 884951223. Here: Example 12.1, pp. 12.2–3

संदर्भ

Immerman, Neil. Descriptive Complexity, 1999, Springer-Verlag.
Libkin, Leonid. Elements of Finite Model Theory, 2004, Springer.श्रेणी: निश्चित अंक (गणित)

[1] C.A. Gunter; D.S. Scott (1990). "Semantic Domains". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 633–674. ISBN 0-444-88074-7. Here: pp. 636–638

[2] N. Immerman, Relational queries computable in polynomial time, Information and Control 68 (1–3) (1986) 86–104.

[3] Immerman, Neil (1982). "Relational Queries Computable in Polynomial Time". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 147–152. doi:10.1145/800070.802187. Revised version in Information and Control, 68 (1986), 86–104.

[4] Vardi, Moshe Y. (1982). "The Complexity of Relational Query Languages". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 137–146. doi:10.1145/800070.802186.

[5] Charguéraud, Arthur (2010). "The Optimal Fixed Point Combinator" (PDF). Interactive Theorem Proving. 6172: 195–210. doi:10.1007/978-3-642-14052-5_15. Retrieved 30 October 2021.

[6] Shamir, Adi (October 1976). The fixedpoints of recursive definitions (Ph.D. thesis). Weizmann Institute of Science. OCLC 884951223. Here: Example 12.1, pp. 12.2–3

[1]

[2]

[3]

[4]

[5]

[6]

कम से कम निश्चित बिंदु

Contents