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

From Vigyanwiki
(Created page with "Image:SuiteSpecker.svg|thumb|200px|एक स्पेकर अनुक्रम। तब<sup>वां</sup> x का अंक<sub>''k''</sub> 4 है अगर ''n''...")
 
No edit summary
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) द्वारा निम्नलिखित निर्माण का वर्णन किया गया है। माना ए [[प्राकृतिक संख्या|प्राकृतिक संख्याओं]] का कोई पुनरावर्ती गणना योग्य सेट है जो [[निर्णायक सेट]] नहीं है, और चलो (एआई) पुनरावृत्ति के बिना ए की गणना योग्य गणना हो। परिमेय संख्याओं के अनुक्रम (''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>'' का अनुमान लगाना संभव है
:<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) ऐसा होगा कि |qj - qi| <1/n सभी i,j > r(n) के लिए। r की गणना करने के लिए, i के बड़े और बड़े मानों के लिए x के बाइनरी विस्तार की तुलना qi के बाइनरी विस्तार से करें। क्यूई की परिभाषा एकल बाइनरी अंक को 0 से 1 तक जाने का कारण बनती है जब भी मैं 1 से बढ़ता हूं। इस प्रकार कुछ एन होगा जहां एक्स का एक बड़ा प्रारंभिक खंड पहले से ही क्यूएन द्वारा निर्धारित किया गया है कि उस सेगमेंट में कोई अतिरिक्त बाइनरी अंक नहीं है। कभी भी चालू किया जा सकता है, जिससे i,j > n के लिए qi और qj के बीच की दूरी का अनुमान लगाया जा सकता है।


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


== यह भी देखें ==
== यह भी देखें ==

Revision as of 15:10, 11 February 2023

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

संगणनीयता सिद्धांत में, एक स्पेकर अनुक्रम परिमेय संख्याओं का एक संगणनीय, नीरस रूप से बढ़ता हुआ, परिबद्ध अनुक्रम है, जिसका सर्वोच्च एक संगणनीय वास्तविक संख्या नहीं है। इस तरह के अनुक्रम का पहला उदाहरण अर्न्स्ट स्पेकर (1949) द्वारा बनाया गया था।

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

उलटा गणित के कार्यक्रम में कम से कम ऊपरी बाध्य सिद्धांत का भी विश्लेषण किया गया है, जहां इस सिद्धांत की सटीक ताकत निर्धारित की गई है। उस कार्यक्रम की शब्दावली में, कम से कम ऊपरी बाध्य सिद्धांत RCA0 पर ACA0 के बराबर है। वास्तव में, आगे के निहितार्थ का प्रमाण, यानी कि कम से कम ऊपरी बाध्य सिद्धांत ACA0 का तात्पर्य है, कम से कम ऊपरी बाध्य सिद्धांत में सर्वोच्चता की गैर-संगणनीयता के पाठ्यपुस्तक प्रमाण (सिम्पसन, 1999 देखें) से आसानी से प्राप्त किया जाता है।

निर्माण

कुशनेर (1984) द्वारा निम्नलिखित निर्माण का वर्णन किया गया है। माना ए प्राकृतिक संख्याओं का कोई पुनरावर्ती गणना योग्य सेट है जो निर्णायक सेट नहीं है, और चलो (एआई) पुनरावृत्ति के बिना ए की गणना योग्य गणना हो। परिमेय संख्याओं के अनुक्रम (qn) को नियम से परिभाषित कीजिए

यह स्पष्ट है कि प्रत्येक क्यूएन गैर-नकारात्मक और तर्कसंगत है, और अनुक्रम क्यूएन सख्ती से बढ़ रहा है। इसके अलावा, क्योंकि एआई में कोई पुनरावृत्ति नहीं है, श्रृंखला के विरुद्ध प्रत्येक qn का अनुमान लगाना संभव है

इस प्रकार सेंक (qn) ऊपर 1 से घिरा हुआ है। शास्त्रीय रूप से, इसका मतलब यह है कि qn का एक सर्वोच्च x है।

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

यदि ऐसा कोई फ़ंक्शन आर गणना योग्य था, तो यह निम्नानुसार ए के लिए निर्णय प्रक्रिया का नेतृत्व करेगा। एक इनपुट k दिया गया है, r(2k+1) की गणना करें। यदि k अनुक्रम (ai) में प्रकट होता है, तो इससे अनुक्रम (qi) में 2−k-1 की वृद्धि होगी, लेकिन ऐसा तब नहीं हो सकता जब (qi) के सभी तत्व प्रत्येक के 2−k-1 के भीतर हों। अन्य। इस प्रकार, यदि k की गणना ai में की जा रही है, तो इसे r(2k+1) से कम i के मान के लिए गणना की जानी चाहिए। यह संभावित स्थानों की एक सीमित संख्या को छोड़ देता है जहाँ k की गणना की जा सकती है। निर्णय प्रक्रिया को पूरा करने के लिए, इन्हें प्रभावी तरीके से जांचें और फिर 0 या 1 लौटाएं, इस पर निर्भर करता है कि k पाया गया है या नहीं।

यह भी देखें

संदर्भ

  • 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=85117’