स्पेकर अनुक्रम: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Image:SuiteSpecker.svg|thumb|200px|एक स्पेकर अनुक्रम। ''x<sub>k</sub>'' का nवां अंक '''4''' है यदि n ≤ k और nवीं [[ट्यूरिंग मशीन|परिगणन युक्ति]] एक संगणनीय गोडेल संख्यांकन में k चरणों के बाद इनपुट ''n'' पर रुक जाती है; अन्यथा यह '''3''' है।]][[संगणनीयता सिद्धांत]] में, | [[Image:SuiteSpecker.svg|thumb|200px|एक स्पेकर अनुक्रम। ''x<sub>k</sub>'' का nवां अंक '''4''' है यदि n ≤ k और nवीं [[ट्यूरिंग मशीन|परिगणन युक्ति]] एक संगणनीय गोडेल संख्यांकन में k चरणों के बाद इनपुट ''n'' पर रुक जाती है; अन्यथा यह '''3''' है।]][[संगणनीयता सिद्धांत]] में, '''स्पेकर अनुक्रम''' परिमेय संख्याओं का एक संगणनीय, एकदिष्ट वर्धमान, परिबद्ध [[अनुक्रम]] है, जिसका महत्तम एक संगणनीय वास्तविक संख्या नहीं है। इस प्रकार के अनुक्रम का पहला उदाहरण [[अर्नस्ट स्पेकर|अर्न्स्ट स्पेकर]] (1949) द्वारा निर्मित किया गया था। | ||
संगणनीय विश्लेषण के लिए स्पेकर अनुक्रमों के अस्तित्व के परिणाम उपस्थित हैं। इस प्रकार के अनुक्रमों का अस्तित्व है, इस तथ्य का अर्थ है कि सभी [[गणना योग्य वास्तविक संख्या|संगणनीय वास्तविक संख्याओं]] का संग्रह, यहाँ तक कि केवल संगणनीय अनुक्रमों पर विचार करने पर वास्तविक विश्लेषण के [[कम से कम ऊपरी बाध्य सिद्धांत|न्यूनतम उपरि परिबंध सिद्धांत]] को संतुष्ट नहीं करता है। इस जटिलता को हल करने की एक सामान्य विधि केवल अभिसरण के मापांक के साथ सम्बद्धता वाले अनुक्रमों पर विचार करना है; किसी स्पेकर अनुक्रम में अभिसरण का संगणनीय मापांक नहीं है। अधिक सामान्यतः एक स्पेकर अनुक्रम को न्यूनतम उपरि परिबंध सिद्धांत के लिए एक ''पुनरावर्ती प्रति उदाहरण'' कहा जाता है, जो कि एक ऐसी संरचना है जो यह दर्शाती है कि यह प्रमेय तब असत्य है जब यह संगणनीय वास्तविक संख्याओं तक ही सीमित है। | |||
[[उलटा गणित]] के कार्यक्रम में | [[उलटा गणित|व्युत्क्रम गणित]] के कार्यक्रम में न्यूनतम उपरि परिबंध सिद्धांत का भी विश्लेषण किया गया है, जहाँ इस सिद्धांत की यथार्थ क्षमता निर्धारित की गई है। इस कार्यक्रम की शब्दावली में न्यूनतम उपरि परिबंध सिद्धांत, RCA<sub>0</sub> पर ACA<sub>0</sub> के समतुल्य है। वास्तव में, अग्र निहितार्थ का प्रमाण (अर्थात् कि न्यूनतम उपरि परिबंध सिद्धांत का तात्पर्य ACA<sub>0</sub> है) न्यूनतम उपरि परिबंध सिद्धांत में महत्तम की गैर-संगणनीयता के पाठ्यपुस्तक प्रमाण (सिम्पसन, 1999 देखें) से आसानी से प्राप्त किया जाता है। | ||
== निर्माण == | == निर्माण == | ||
कुशनेर (1984) द्वारा निम्नलिखित | कुशनेर (1984) द्वारा निम्नलिखित संरचना का वर्णन किया गया है। माना ''A'' [[प्राकृतिक संख्या|प्राकृतिक संख्याओं]] का एक पुनरावर्ती संगणनीय समुच्चय है जो [[निर्णायक सेट|निर्धार्य]] नहीं है, और माना (''a<sub>i</sub>'') पुनरावृत्ति के बिना ''A'' की संगणनीय गणना है। परिमेय संख्याओं के अनुक्रम (''q<sub>n</sub>'') को निम्न नियम से परिभाषित करने पर, | ||
:<math>q_n = \sum_{i = 0}^n 2^{-a_i - 1}.</math> | :<math>q_n = \sum_{i = 0}^n 2^{-a_i - 1}.</math> | ||
यह स्पष्ट है कि प्रत्येक | यह स्पष्ट है कि प्रत्येक ''q<sub>n</sub>'' गैर-ऋणात्मक और परिमेय है, और अनुक्रम ''q<sub>n</sub>'' निरंतर वर्धमान है। इसके अतिरिक्त निम्न श्रृंखला के विरुद्ध प्रत्येक ''q<sub>n</sub>'' का अनुमान लगाना संभव है, क्योंकि ''a<sub>i</sub>'' में कोई पुनरावृत्ति नहीं है, | ||
:<math>\sum_{i = 0}^\infty 2^{-i-1} = 1.</math> | :<math>\sum_{i = 0}^\infty 2^{-i-1} = 1.</math> | ||
इस प्रकार | इस प्रकार अनुक्रम (''q<sub>n</sub>'') ऊपर 1 से परिबद्ध है। चिरसम्मत रूप से, इसका अर्थ यह है कि ''q<sub>n</sub>'' का एक महत्तम ''x'' है। | ||
यह | यह दर्शाया गया है कि ''x'' एक संगणनीय वास्तविक संख्या नहीं है। यह प्रमाण संगणनीय वास्तविक संख्याओं के बारे में एक विशेष तथ्य का उपयोग करता है। यदि ''x'' संगणनीय थे तो एक संगणनीय फलन ''r''(''n'') इस प्रकार है कि सभी ''i,j'' > ''r''(''n'') के लिए, |''q<sub>j</sub> - q<sub>i</sub>''| <1/''n''। ''r'' की गणना करने के लिए, ''i'' के बड़े से बड़े मानों के लिए x के द्विआधारी विस्तार की तुलना ''q<sub>i</sub>'' के द्विआधारी विस्तार से करें। ''q<sub>i</sub>'' की परिभाषा ''i के'' प्रत्येक बार 1 बढ़ने पर एकल द्विआधारी अंक के 0 से 1 तक जाने का कारण बनती है। इस प्रकार कुछ ''n'' ऐसे होंगे जहाँ ''x'' का एक बड़ा पर्याप्त प्रारंभिक खंड ''q<sub>n</sub>'' द्वारा इस प्रकार पहले से ही निर्धारित किया गया है कि इस खण्ड में ऐसा कोई अतिरिक्त द्विआधारी अंक नहीं है, जो कभी भी प्रारंभ किया जा सका हो, जिससे ''i,j'' > ''n'' के लिए ''q<sub>i</sub>'' और ''q<sub>j</sub>'' के बीच की दूरी को अनुमानित किया जा सकता है। | ||
यदि | यदि ऐसे कोई फलन ''r'' संगणनीय थे, तो यह निम्नानुसार ''A'' के लिए निर्णय प्रक्रिया का नेतृत्व करता है। एक इनपुट ''k'' दिया गया है, तब ''r''(2<sup>''k+1''</sup>) की गणना करें। यदि ''k'' अनुक्रम (''a<sub>i</sub>'') में प्रकट होता है, तो इससे अनुक्रम (''q<sub>i</sub>'') में 2''<sup>−k-1</sup>'' की वृद्धि होती है, लेकिन ऐसा तब नहीं हो सकता जब (''q<sub>i</sub>'') के सभी तत्व एक-दूसरे के 2''<sup>−k-1</sup>'' के भीतर हों। इस प्रकार, यदि ''k'' की गणना ''a<sub>i</sub>'' में की जा रही है, तो इसकी गणना ''i'' के ''r''(2''<sup>k+1</sup>'') से कम मान के लिए की जानी चाहिए। यह संभावित स्थानों की एक सीमित संख्या को छोड़ देता है जहाँ ''k'' की गणना की जा सकती है। निर्णय प्रक्रिया को पूरा करने के लिए, प्रभावी विधि से इनकी जाँच करें और फिर ''k'' की प्राप्ति के आधार पर 0 या 1 की पुनःपूर्ति करें। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 16:08, 12 February 2023
संगणनीयता सिद्धांत में, स्पेकर अनुक्रम परिमेय संख्याओं का एक संगणनीय, एकदिष्ट वर्धमान, परिबद्ध अनुक्रम है, जिसका महत्तम एक संगणनीय वास्तविक संख्या नहीं है। इस प्रकार के अनुक्रम का पहला उदाहरण अर्न्स्ट स्पेकर (1949) द्वारा निर्मित किया गया था।
संगणनीय विश्लेषण के लिए स्पेकर अनुक्रमों के अस्तित्व के परिणाम उपस्थित हैं। इस प्रकार के अनुक्रमों का अस्तित्व है, इस तथ्य का अर्थ है कि सभी संगणनीय वास्तविक संख्याओं का संग्रह, यहाँ तक कि केवल संगणनीय अनुक्रमों पर विचार करने पर वास्तविक विश्लेषण के न्यूनतम उपरि परिबंध सिद्धांत को संतुष्ट नहीं करता है। इस जटिलता को हल करने की एक सामान्य विधि केवल अभिसरण के मापांक के साथ सम्बद्धता वाले अनुक्रमों पर विचार करना है; किसी स्पेकर अनुक्रम में अभिसरण का संगणनीय मापांक नहीं है। अधिक सामान्यतः एक स्पेकर अनुक्रम को न्यूनतम उपरि परिबंध सिद्धांत के लिए एक पुनरावर्ती प्रति उदाहरण कहा जाता है, जो कि एक ऐसी संरचना है जो यह दर्शाती है कि यह प्रमेय तब असत्य है जब यह संगणनीय वास्तविक संख्याओं तक ही सीमित है।
व्युत्क्रम गणित के कार्यक्रम में न्यूनतम उपरि परिबंध सिद्धांत का भी विश्लेषण किया गया है, जहाँ इस सिद्धांत की यथार्थ क्षमता निर्धारित की गई है। इस कार्यक्रम की शब्दावली में न्यूनतम उपरि परिबंध सिद्धांत, RCA0 पर ACA0 के समतुल्य है। वास्तव में, अग्र निहितार्थ का प्रमाण (अर्थात् कि न्यूनतम उपरि परिबंध सिद्धांत का तात्पर्य ACA0 है) न्यूनतम उपरि परिबंध सिद्धांत में महत्तम की गैर-संगणनीयता के पाठ्यपुस्तक प्रमाण (सिम्पसन, 1999 देखें) से आसानी से प्राप्त किया जाता है।
निर्माण
कुशनेर (1984) द्वारा निम्नलिखित संरचना का वर्णन किया गया है। माना A प्राकृतिक संख्याओं का एक पुनरावर्ती संगणनीय समुच्चय है जो निर्धार्य नहीं है, और माना (ai) पुनरावृत्ति के बिना A की संगणनीय गणना है। परिमेय संख्याओं के अनुक्रम (qn) को निम्न नियम से परिभाषित करने पर,
यह स्पष्ट है कि प्रत्येक qn गैर-ऋणात्मक और परिमेय है, और अनुक्रम qn निरंतर वर्धमान है। इसके अतिरिक्त निम्न श्रृंखला के विरुद्ध प्रत्येक qn का अनुमान लगाना संभव है, क्योंकि ai में कोई पुनरावृत्ति नहीं है,
इस प्रकार अनुक्रम (qn) ऊपर 1 से परिबद्ध है। चिरसम्मत रूप से, इसका अर्थ यह है कि qn का एक महत्तम x है।
यह दर्शाया गया है कि x एक संगणनीय वास्तविक संख्या नहीं है। यह प्रमाण संगणनीय वास्तविक संख्याओं के बारे में एक विशेष तथ्य का उपयोग करता है। यदि x संगणनीय थे तो एक संगणनीय फलन r(n) इस प्रकार है कि सभी i,j > r(n) के लिए, |qj - qi| <1/n। r की गणना करने के लिए, i के बड़े से बड़े मानों के लिए x के द्विआधारी विस्तार की तुलना qi के द्विआधारी विस्तार से करें। qi की परिभाषा i के प्रत्येक बार 1 बढ़ने पर एकल द्विआधारी अंक के 0 से 1 तक जाने का कारण बनती है। इस प्रकार कुछ n ऐसे होंगे जहाँ x का एक बड़ा पर्याप्त प्रारंभिक खंड qn द्वारा इस प्रकार पहले से ही निर्धारित किया गया है कि इस खण्ड में ऐसा कोई अतिरिक्त द्विआधारी अंक नहीं है, जो कभी भी प्रारंभ किया जा सका हो, जिससे i,j > n के लिए qi और qj के बीच की दूरी को अनुमानित किया जा सकता है।
यदि ऐसे कोई फलन r संगणनीय थे, तो यह निम्नानुसार A के लिए निर्णय प्रक्रिया का नेतृत्व करता है। एक इनपुट k दिया गया है, तब r(2k+1) की गणना करें। यदि k अनुक्रम (ai) में प्रकट होता है, तो इससे अनुक्रम (qi) में 2−k-1 की वृद्धि होती है, लेकिन ऐसा तब नहीं हो सकता जब (qi) के सभी तत्व एक-दूसरे के 2−k-1 के भीतर हों। इस प्रकार, यदि k की गणना ai में की जा रही है, तो इसकी गणना i के r(2k+1) से कम मान के लिए की जानी चाहिए। यह संभावित स्थानों की एक सीमित संख्या को छोड़ देता है जहाँ k की गणना की जा सकती है। निर्णय प्रक्रिया को पूरा करने के लिए, प्रभावी विधि से इनकी जाँच करें और फिर k की प्राप्ति के आधार पर 0 या 1 की पुनःपूर्ति करें।
यह भी देखें
संदर्भ
- Douglas Bridges and Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.
- B.A. Kushner (1984), Lectures on constructive mathematical analysis, American Mathematical Society, Translations of Mathematical Monographs v. 60.
- Jakob G. Simonsen (2005), "Specker sequences revisited", Mathematical Logic Quarterly, v. 51, pp. 532–540. doi:10.1002/malq.200410048
- S. Simpson (1999), Subsystems of second-order arithmetic, Springer.
- E. Specker (1949), "Nicht konstruktiv beweisbare Sätze der Analysis" Journal of Symbolic Logic, v. 14, pp. 145–158.
