स्पेकर अनुक्रम

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

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

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

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

निर्माण

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

$q_{n}=\sum _{i=0}^{n}2^{-a_{i}-1}.$

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

$\sum _{i=0}^{\infty }2^{-i-1}=1.$

इस प्रकार सेंक (q_n) ऊपर 1 से घिरा हुआ है। शास्त्रीय रूप से, इसका मतलब यह है कि q_n का एक सर्वोच्च 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.