स्पेकर अनुक्रम: Difference between revisions

From Vigyanwiki
(Created page with "Image:SuiteSpecker.svg|thumb|200px|एक स्पेकर अनुक्रम। तब<sup>वां</sup> x का अंक<sub>''k''</sub> 4 है अगर ''n''...")
 
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[Image:SuiteSpecker.svg|thumb|200px|एक स्पेकर अनुक्रम। तब<sup>वां</sup> x का अंक<sub>''k''</sub> 4 है अगर ''n'' ≤ ''k'' और एक संगणनीय गोडेल नंबरिंग में ''n'' [[ट्यूरिंग मशीन]] ''k'' चरणों के बाद इनपुट ''n'' पर रुकती है; अन्यथा यह 3 है।]][[संगणनीयता सिद्धांत]] में, एक स्पेकर [[अनुक्रम]] एक संगणनीय फलन है, अनुक्रम#बढ़ता_और_घटता, अनुक्रम#परिमेय संख्याओं का परिबद्ध अनुक्रम जिसका सर्वोच्च एक संगणनीय वास्तविक संख्या नहीं है। इस तरह के अनुक्रम का पहला उदाहरण [[अर्नस्ट स्पेकर]] (1949) द्वारा बनाया गया था।
[[Image:SuiteSpecker.svg|thumb|200px|एक स्पेकर अनुक्रम। ''x<sub>k</sub>'' का nवां अंक '''4''' है यदि n ≤ k और nवीं [[ट्यूरिंग मशीन|परिगणन युक्ति]] एक संगणनीय गोडेल संख्यांकन में k चरणों के बाद इनपुट ''n'' पर रुक जाती है; अन्यथा यह '''3''' है।]][[संगणनीयता सिद्धांत]] में, '''स्पेकर अनुक्रम''' परिमेय संख्याओं का एक संगणनीय, एकदिष्ट वर्धमान, परिबद्ध [[अनुक्रम]] है, जिसका महत्तम एक संगणनीय वास्तविक संख्या नहीं है। इस प्रकार के अनुक्रम का पहला उदाहरण [[अर्नस्ट स्पेकर|अर्न्स्ट स्पेकर]] (1949) द्वारा निर्मित किया गया था।


कंप्यूटेशनल विश्लेषण के लिए स्पेकर अनुक्रमों के अस्तित्व के परिणाम हैं। तथ्य यह है कि इस तरह के अनुक्रम मौजूद हैं इसका मतलब है कि सभी [[गणना योग्य वास्तविक संख्या]]ओं का संग्रह वास्तविक विश्लेषण के [[कम से कम ऊपरी बाध्य सिद्धांत]] को संतुष्ट नहीं करता है, भले ही केवल गणना योग्य अनुक्रमों पर विचार किया जाए।
संगणनीय विश्लेषण के लिए स्पेकर अनुक्रमों के अस्तित्व के परिणाम उपस्थित हैं। इस प्रकार के अनुक्रमों का अस्तित्व है, इस तथ्य का अर्थ है कि सभी [[गणना योग्य वास्तविक संख्या|संगणनीय वास्तविक संख्याओं]] का संग्रह, यहाँ तक कि केवल संगणनीय अनुक्रमों पर विचार करने पर वास्तविक विश्लेषण के [[कम से कम ऊपरी बाध्य सिद्धांत|न्यूनतम उपरि परिबंध सिद्धांत]] को संतुष्ट नहीं करता है। इस जटिलता को हल करने की एक सामान्य विधि केवल अभिसरण के मापांक के साथ सम्बद्धता वाले अनुक्रमों पर विचार करना है; किसी स्पेकर अनुक्रम में अभिसरण का संगणनीय मापांक नहीं है। अधिक सामान्यतः एक स्पेकर अनुक्रम को न्यूनतम उपरि परिबंध सिद्धांत के लिए एक ''पुनरावर्ती प्रति उदाहरण'' कहा जाता है, जो कि एक ऐसी संरचना है जो यह दर्शाती है कि यह प्रमेय तब असत्य है जब यह संगणनीय वास्तविक संख्याओं तक ही सीमित है।
इस कठिनाई को हल करने का एक सामान्य तरीका केवल उन अनुक्रमों पर विचार करना है जो अभिसरण के मापांक के साथ हैं; किसी स्पेकर अनुक्रम में अभिसरण का संगणनीय मापांक नहीं है।
अधिक आम तौर पर, एक स्पेकर अनुक्रम को कम से कम ऊपरी बाध्य सिद्धांत के लिए एक ''पुनरावर्ती प्रति उदाहरण'' कहा जाता है, यानी एक निर्माण जो दिखाता है कि यह प्रमेय गलत है जब संगणनीय वास्तविकताओं तक सीमित है।


[[उलटा गणित]] के कार्यक्रम में कम से कम ऊपरी बाध्य सिद्धांत का भी विश्लेषण किया गया है, जहां इस सिद्धांत की सटीक ताकत निर्धारित की गई है। उस कार्यक्रम की शब्दावली में, कम से कम ऊपरी बाध्य सिद्धांत एसीए के बराबर है<sub>0</sub> आरसीए से अधिक<sub>0</sub>. वास्तव में, आगे के निहितार्थ का प्रमाण, यानी कि कम से कम ऊपरी बाध्य सिद्धांत एसीए का तात्पर्य है<sub>0</sub>, कम से कम ऊपरी बाध्य सिद्धांत में सुप्रीमम की गैर-कम्प्यूटेबिलिटी के पाठ्यपुस्तक प्रमाण (सिम्पसन, 1999 देखें) से आसानी से प्राप्त किया जाता है।
[[उलटा गणित|व्युत्क्रम गणित]] के कार्यक्रम में न्यूनतम उपरि परिबंध सिद्धांत का भी विश्लेषण किया गया है, जहाँ इस सिद्धांत की यथार्थ क्षमता निर्धारित की गई है। इस कार्यक्रम की शब्दावली में न्यूनतम उपरि परिबंध सिद्धांत, RCA<sub>0</sub> पर ACA<sub>0</sub> के समतुल्य है। वास्तव में, अग्र निहितार्थ का प्रमाण (अर्थात् कि न्यूनतम उपरि परिबंध सिद्धांत का तात्पर्य ACA<sub>0</sub> है) न्यूनतम उपरि परिबंध सिद्धांत में महत्तम की गैर-संगणनीयता के पाठ्यपुस्तक प्रमाण (सिम्पसन, 1999 देखें) से आसानी से प्राप्त किया जाता है।


== निर्माण ==
== निर्माण ==


कुशनेर (1984) द्वारा निम्नलिखित निर्माण का वर्णन किया गया है। चलो ए [[प्राकृतिक संख्या]]ओं का कोई पुनरावर्ती गणना योग्य सेट है जो [[निर्णायक सेट]] नहीं है, और चलो (ए<sub>''i''</sub>) पुनरावृत्ति के बिना A की संगणनीय गणना हो। अनुक्रम परिभाषित करें (क्यू<sub>''n''</sub>) नियम के साथ परिमेय संख्याओं का
कुशनेर (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>
यह स्पष्ट है कि प्रत्येक क्यू<sub>''n''</sub> गैर-ऋणात्मक और तर्कसंगत है, और यह अनुक्रम q है<sub>''n''</sub> सख्ती से बढ़ रहा है। इसके अलावा, क्योंकि ए<sub>''i''</sub> कोई पुनरावृत्ति नहीं है, प्रत्येक q का अनुमान लगाना संभव है<sub>''n''</sub> श्रृंखला के खिलाफ
यह स्पष्ट है कि प्रत्येक ''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> एक सर्वोच्च एक्स है।
इस प्रकार अनुक्रम (''q<sub>n</sub>'') ऊपर 1 से परिबद्ध है। चिरसम्मत रूप से, इसका अर्थ यह है कि ''q<sub>n</sub>'' का एक महत्तम ''x'' है।


यह दिखाया गया है कि x एक संगणनीय वास्तविक संख्या नहीं है। प्रमाण संगणनीय वास्तविक संख्याओं के बारे में एक विशेष तथ्य का उपयोग करता है। यदि x संगणनीय होता तो एक संगणनीय फलन r(n) ऐसा होता कि |q<sub>''j''</sub> - क्यू<sub>''i''</sub>| <1/n सभी i,j > r(n) के लिए। आर की गणना करने के लिए, एक्स के बाइनरी विस्तार की तुलना क्यू के बाइनरी विस्तार से करें<sub>''i''</sub> i के बड़े और बड़े मानों के लिए। क्यू की परिभाषा<sub>''i''</sub> एक एकल बाइनरी अंक 0 से 1 तक जाने के लिए हर बार i 1 से बढ़ता है। इस प्रकार कुछ n होगा जहां x का एक बड़ा पर्याप्त प्रारंभिक खंड पहले से ही q द्वारा निर्धारित किया गया है<sub>''n''</sub> कि उस सेगमेंट में कोई अतिरिक्त बाइनरी अंक कभी भी चालू नहीं किया जा सकता है, जिससे q के बीच की दूरी का अनुमान लगाया जा सकता है<sub>''i''</sub> और क्यू<sub>''j''</sub> मैं, जे > एन के लिए।
यह दर्शाया गया है कि ''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>'' के बीच की दूरी को अनुमानित किया जा सकता है।


यदि ऐसा कोई फ़ंक्शन आर गणना योग्य था, तो यह निम्नानुसार ए के लिए निर्णय प्रक्रिया का नेतृत्व करेगा। एक इनपुट के दिया गया है, आर की गणना करें (2<sup>के+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>, इसे r(2) से कम i के मान के लिए गिना जाना चाहिए<sup>के+1</sup>). यह संभावित स्थानों की एक सीमित संख्या को छोड़ देता है जहाँ k की गणना की जा सकती है। निर्णय प्रक्रिया को पूरा करने के लिए, इन्हें प्रभावी तरीके से जांचें और फिर 0 या 1 लौटाएं, इस पर निर्भर करता है कि k पाया गया है या नहीं।
यदि ऐसे कोई फलन ''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 की पुनःपूर्ति करें।


== यह भी देखें ==
== यह भी देखें ==
Line 28: Line 26:
* S. Simpson (1999), ''Subsystems of second-order arithmetic'', Springer.  
* 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.
* E. Specker (1949), "Nicht konstruktiv beweisbare Sätze der Analysis"  ''Journal of Symbolic Logic'', v. 14, pp. 145–158.
[[Category: संगणनीय विश्लेषण]]


[[Category: Machine Translated Page]]
[[Category:Created On 03/02/2023]]
[[Category:Created On 03/02/2023]]
[[Category:Machine Translated Page]]
[[Category:Templates Vigyan Ready]]
[[Category:संगणनीय विश्लेषण]]

Latest revision as of 12:55, 14 February 2023

एक स्पेकर अनुक्रम। xk का nवां अंक 4 है यदि n ≤ k और nवीं परिगणन युक्ति एक संगणनीय गोडेल संख्यांकन में k चरणों के बाद इनपुट n पर रुक जाती है; अन्यथा यह 3 है।

संगणनीयता सिद्धांत में, स्पेकर अनुक्रम परिमेय संख्याओं का एक संगणनीय, एकदिष्ट वर्धमान, परिबद्ध अनुक्रम है, जिसका महत्तम एक संगणनीय वास्तविक संख्या नहीं है। इस प्रकार के अनुक्रम का पहला उदाहरण अर्न्स्ट स्पेकर (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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=स्पेकर_अनुक्रम&oldid=85596’