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

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

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

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

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

निर्माण

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

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

यह स्पष्ट है कि प्रत्येक क्यू_n गैर-ऋणात्मक और तर्कसंगत है, और यह अनुक्रम q है_n सख्ती से बढ़ रहा है। इसके अलावा, क्योंकि ए_i कोई पुनरावृत्ति नहीं है, प्रत्येक q का अनुमान लगाना संभव है_n श्रृंखला के खिलाफ

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

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

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

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