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

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

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

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

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

निर्माण

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

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

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

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

इस प्रकार अनुक्रम (q_n) ऊपर 1 से परिबद्ध है। चिरसम्मत रूप से, इसका अर्थ यह है कि q_n का एक महत्तम x है।

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

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