ट्यूरिंग न्यूनन

गणितीयता सिद्धांत में, एक निर्णय समस्या $A$ से एक निर्णय समस्या $B$ की त्यौरिंग संक्षेपण एक ऑरेकल मशीन होती है जो $B$ के लिए एक ऑरेकल के द्वारा समस्या $A$ का निर्णय करती है (रोजर्स 1967, सोरे 1987)। इसे एक ऐसे एल्गोरिदम के रूप में समझा जा सकता है जो समस्या $B$ को हल करने के लिए उपलब्ध होने पर समस्या $A$ को हल करने के लिए उपयोग किया जा सकता है। इस संक्षेपण को फ़ंक्शन समस्याओं पर भी समानांतर लागू किया जा सकता है।

यदि $A$ से $B$ की त्यौरिंग संक्षेपण मौजूद होता है, तो $B$ के लिए के लिए उपयोग होने वाले प्रत्येक एल्गोरिदम का उपयोग करके $A$ के लिए एक एल्गोरिदम बनाया जा सकता है, जहां A को त्यौरिंग संक्षेपण करने वाली ऑरेकल मशीन B के लिए ऑरेकल से पूछताछ करती है।हालांकि, क्योंकि ऑरेकल मशीन ऑरेकल की बड़ी संख्या में पूछताछ कर सकती है, इसलिए परिणामी एल्गोरिदम $B$ या $A$ के एल्गोरिदम या ऑरेकल मशीन के कंप्यूटिंग से असिम्प्टोटिक रूप से अधिक समय की आवश्यकता हो सकती है। पोलिनोमियल समय में ऑरेकल मशीन चलने वाला एक त्यौरिंग संक्षेपण को कुक संक्षेपण के रूप में जाना जाता है।

रिलेटिव कम्प्यूटेबिलिटी की पहली औपचारिक परिभाषा, जिसे रिलेटिव रिड्यूसिबिलिटी कहा जाता है, 1939 में ऑरेकल मशीनों के संदर्भ में एलन ट्यूरिंग द्वारा दी गई थी। बाद में 1943 और 1952 में स्टीफन क्लेन ने पुनरावर्ती कार्यों के संदर्भ में एक समतुल्य अवधारणा को परिभाषित किया। 1944 में एमिल पोस्ट ने अवधारणा को संदर्भित करने के लिए "ट्यूरिंग रिड्यूसिबिलिटी" शब्द का उपयोग किया।

परिभाषा

दो सेट दिए गए हैं $A,B\subseteq \mathbb {N}$ प्राकृतिक संख्या, हम कहते हैं कि $A$ ट्यूरिंग $B$ तक रिड्यूसिबल है और लिखें

$A\leq _{T}B$

यदि एक ओरेकल मशीन है जो ओरेकल बी के साथ चलाई जाती हुई ए के संकेतक फ़ंक्शन की गणना करती है। इस स्थिति में, हम यह भी कहते हैं कि ए 'बी-पुनरावर्ती' और 'बी-गणना योग्य' है।

यदि एक ऑरेकल मशीन है जो बी के साथ चलाई जाती हुई एक आंशिक फ़ंक्शन की हिसाब कर सकती है जिसका डोमेन ए है, तो ए को 'पुनरावर्ती गणना योग्य सेट' और 'बी-कम्प्यूटेशनल इन्युमरेबल' कहा जाता है।

हम कहते हैं $A$ ट्यूरिंग के बराबर है $B$ और लिखा $A\equiv _{T}B\,$ अगर दोनों $A\leq _{T}B$ और $B\leq _{T}A.$ ट्यूरिंग समतुल्य सेटों के तुल्यता वर्गों को ट्यूरिंग डिग्री कहा जाता है। एक सेट की ट्यूरिंग डिग्री $X$ लिखा है ${\textbf {deg}}(X)$.

एक सेट दिया ${\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )$, एक सेट $A\subseteq \mathbb {N}$ ट्यूरिंग हार्ड के लिए कहा जाता है ${\mathcal {X}}$ अगर $X\leq _{T}A$ सभी के लिए $X\in {\mathcal {X}}$. अगर अतिरिक्त $A\in {\mathcal {X}}$ तब $A$ ट्यूरिंग के लिए पूर्ण कहा जाता है ${\mathcal {X}}$।

कम्प्यूटेशनल सार्वभौमिकता के लिए ट्यूरिंग पूर्णता का संबंध

त्यौरिंग पूर्णता, जैसा कि पहले ही परिभाषित किया गया है, कंप्यूटेशनल विश्वसनीयता के दृष्टिकोण में केवल आंशिक रूप से संबंधित होती है। विशेष रूप से, एक त्यौरिंग मशीन एक विश्वसनीय त्यौरिंग मशीन है यदि इसकी रुकने की समस्या (यानी, इनपुट का सेट जिसके लिए यह अंततः रुक जाती है) बहुएक समस्या है | इस प्रकार, एक मशीन के कम्प्यूटेशनल रूप से सार्वभौमिक होने के लिए एक आवश्यक लेकिन अपर्याप्त स्थिति यह है कि सेट के लिए मशीन की हॉल्टिंग समस्या ट्यूरिंग-पूर्ण हो ${\mathcal {X}}$ पुनरावर्ती गणना योग्य सेटों की। यह पर्याप्त नहीं है क्योंकि इसका मतलब यह भी हो सकता है कि, मशीन द्वारा स्वीकार की जाने वाली भाषा स्वयं रिकर्सिव यथार्थ संख्यात्मक न हो।

उदाहरण

यदि $W_{e}$ इनपुट मूल्यों के सेट को निरूपित करें जिसके लिए इंडेक्स ई के साथ ट्यूरिंग मशीन रुक जाती है। फिर सेट $A=\{e\mid e\in W_{e}\}$ और $B=\{(e,n)\mid n\in W_{e}\}$ ट्यूरिंग समतुल्य हैं (यहाँ $(-,-)$ एक प्रभावी युग्मन कार्य को दर्शाता है)। कमी दिखा रहा है $A\leq _{T}B$ इस तथ्य का उपयोग करके बनाया जा सकता है कि $e\in A\Leftrightarrow (e,e)\in B$. एक जोड़ा दिया $(e,n)$, एक नया सूचकांक $i(e,n)$ Smn प्रमेय का उपयोग करके बनाया जा सकता है_mn प्रमेय ऐसा है कि कार्यक्रम द्वारा कोडित $i(e,n)$ इसके इनपुट को अनदेखा करता है और केवल इनपुट एन पर इंडेक्स ई के साथ मशीन की गणना का अनुकरण करता है। विशेष रूप से, index $i(e,n)$ या तो हर इनपुट पर रुकता है या बिना इनपुट के रुकता है। इस प्रकार $i(e,n)\in A\Leftrightarrow (e,n)\in B$ सभी ई और एन के लिए रखती है। क्योंकि फ़ंक्शन i गणना योग्य है, यह दिखाता है $B\leq _{T}A$. यहां प्रस्तुत कटौती न केवल ट्यूरिंग कटौती बल्कि कई-एक कटौती हैं, जिनकी चर्चा नीचे की गई है।

गुण

• प्रत्येक सेट ट्यूरिंग के पूरक के बराबर है।
• प्रत्येक कम्प्यूटेबल सेट ट्यूरिंग प्रत्येक अन्य सेट के लिए रिड्यूसिबल है। क्योंकि किसी भी गणन योग्य सेट की गणना बिना किसी ऑरेकल के की जा सकती है, इसकी गणना एक ऑरेकल मशीन द्वारा की जा सकती है जो दिए गए ऑरेकल को अनदेखा करती है।
• रिश्ता $\leq _{T}$ सकर्मक है: यदि $A\leq _{T}B$ और $B\leq _{T}C$ तब $A\leq _{T}C$. इसके अतिरिक्त, $A\leq _{T}A$ प्रत्येक समुच्चय A के लिए मान्य है, और इस प्रकार संबंध $\leq _{T}$ एक पूर्व आदेश है (यह आंशिक ऑर्डर नहीं है क्योंकि $A\leq _{T}B$ और $B\leq _{T}A$ जरूरी नहीं है $A=B$)।
• सेट के जोड़े हैं $(A,B)$ ऐसा है कि A, B के लिए ट्यूरिंग रिड्यूसिबल नहीं है और B, A के लिए ट्यूरिंग रिड्यूसिबल नहीं है $\leq _{T}$ कुल आदेश नहीं है।
• नीचे सेट के अनंत घटते क्रम हैं $\leq _{T}$. इस प्रकार यह संबंध अच्छी तरह से स्थापित नहीं है।
• हर सेट अपने स्वयं के ट्यूरिंग कूदो के लिए ट्यूरिंग रिड्यूसिबल है, लेकिन सेट का ट्यूरिंग जंप मूल सेट के लिए ट्यूरिंग रिड्यूसिबल नहीं है।

कटौती का उपयोग

क्योंकि सेट $B$ से सेट $A$ तक की प्रत्याकरण में हर बार केवल संक्षेप में एक तत्व के बारे में यह निर्धारित करना होता है कि वह $A$ में है या नहीं, इसलिए यह संख्या $B$ के सदस्यता का केवल संख्यित संख्या प्रश्न पूछ सकती है। जब एक एकल बिट $A$ की गणना करने के लिए इस्तेमाल की जाने वाली जानकारी की मात्रा की चर्चा की जाती है, तो इसे उपयोग फ़ंक्शन द्वारा सटीक बनाया जाता है। सूत्री रूप में, एक प्रत्यास्थापन का उपयोग वह संख्या है जो प्रत्यास्थापन द्वारा $A$ में $n$ की सदस्यता की जांच करते समय सदस्यता $B$ में पूछी गई सबसे बड़ी प्राकृतिक संख्या $m$ को भेजता है।

मजबूत कटौती

त्यौरिंग प्रत्यास्थापन से शक्तिशाली प्रत्यास्थापन उत्पन्न करने के दो सामान्य तरीके होते हैं। पहला तरीका है ऑरेकल प्रश्नों की संख्या और तरीके को सीमित करना।

• सेट $A$ सेट $B$ के लिए बहु-एक रेड्यूसिबल होता है यदि एक पूर्ण गणनीय फ़ंक्शन $f$ ऐसा होता है जिसके अंततः एक तत्व $n$ में है $A$ होगा यदि और केवल यदि $f(n)$ में $B$ में होता है। ऐसी एक फ़ंक्शन त्यौरिंग प्रत्यास्थापन उत्पन्न करने के लिए उपयोगी हो सकती है $f(n)$ की गणना करके, ऑरेकल को प्रश्न पूछकर और फिर परिणाम को व्याख्या करके)।
• सत्यतालेख रेड्यूसन या एक कमजोर सत्यतालेख रेड्यूसन को सभी ऑरेकल प्रश्नों को एक ही समय पर प्रस्तुत करना होता है। सत्यतालेख रेड्यूसन में, रेड्यूसन एक बूलियन फ़ंक्शन (एक सत्यतालेख) भी देता है जिसे प्रश्नों के उत्तरों को दिए जाने पर रेड्यूसन का अंतिम उत्तर उत्पन्न करेगा। कमजोर सत्यतालेख रेड्यूसन में, रेड्यूसन दिए गए उत्तरों पर आधारित औराकल का उपयोग किए बिना आगे की गणना के लिए उपयोग करती है। समकक्षता में, कमजोर सत्यतालेख रेड्यूसन ऐसी होती है जिसमें रेड्यूसन का उपयोग एक गणनीय फ़ंक्शन द्वारा सीमित होता है। इसी कारण से, कमजोर सत्यतालेख रेड्यूसन को कभी-कभी "सीमित त्यौरिंग" रेड्यूसन कहा जाता है।

एक और मजबूत प्रत्यास्थापन धारणा उत्पन्न करने का दूसरा तरीका है त्यौरिंग प्रत्यास्थापन को लागू करने वाले प्रोग्राम के गणनीय संसाधनों को सीमित करना। इन प्रत्यास्थापनों में गणनात्मक जटिलता सिद्धांत की सीमाएं प्रमुख होती हैं जब पी (जटिलता)जैसी उप-गणनात्मक वर्गों का अध्ययन किया जाता है। एक समुच्चय A बहुपद-समय में कमी है | बहुपद-समय एक समुच्चय में घटाया जा सकता है $B$ अगर ट्यूरिंग की कमी है $A$ को $B$ जो बहुपद समय में चलता है। लॉग-स्पेस कमी की अवधारणा समान होती है।

इन प्रत्यास्थापनों में से उत्पन्न होने वाले बदलाव संबंध में, यह मजबूत होते हैं क्योंकि वे समानता वर्गों में और पुनरावृत्ति की तुलना में एक अधिक सटीक भेद प्रदान करते हैं, और त्यौरिंग प्रत्यास्थापनों से अधिक प्रतिबंधकारी आवश्यकताओं को पूरा करते हैं। इसलिए, ऐसी प्रत्यास्थापनें ढूंढ़ना कठिन होता है। एक सेट से दूसरे सेट में कई-एक कटौती का निर्माण करने का कोई रास्ता नहीं हो सकता है, यहाँ तक कि यदि उनीही सेटों के लिए एक त्यौरिंग प्रत्यास्थापन मौजूद हो।

कमजोर कटौती

चर्च-ट्यूरिंग थीसिस के अनुसार, ट्यूरिंग रिडक्शन प्रभावी रूप से गणना योग्य कमी का सबसे सामान्य रूप है। फिर भी, कमजोर कटौती पर भी विचार किया जाता है। तय करना $A$ में अंकगणितीय सेट कहा जाता है $B$ अगर $A$ के साथ पीनो अंकगणितीय के एक सूत्र द्वारा परिभाषित किया जा सकता है जिसमें $B$ एक पैरामीटर के रूप में है। समुच्चय $A$ में अतिगणितीय पदानुक्रम है $B$ यदि कोई पुनरावर्ती क्रमसूचक है $\alpha$ ऐसा है कि $A$ से गणना योग्य है $B^{(\alpha )}$, α-पुनरावृत्त ट्यूरिंग कूद $B$. सापेक्ष निर्माणशीलता की धारणा समुच्चय सिद्धांत में एक महत्वपूर्ण अपचयनशीलता धारणा है।

यह भी देखें

• कार्प कमी

संदर्भ

• M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9.
• S. C. Kleene, 1952. Introduction to Metamathematics. Amsterdam: North-Holland.
• S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics v. 2 n. 59, 379–407.
• Post, E. L. (1944). "Recursively enumerable sets of positive integers and their decision problems" (PDF). Bulletin of the American Mathematical Society. 50 (5): 284–316. doi:10.1090/s0002-9904-1944-08111-1. Retrieved 2015-12-17.
• A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.
• H. Rogers, 1967. Theory of recursive functions and effective computability. McGraw-Hill.
• R. Soare, 1987. Recursively enumerable sets and degrees, Springer.
• Davis, Martin (November 2006). "What is...Turing Reducibility?" (PDF). Notices of the American Mathematical Society. 53 (10): 1218–1219. Retrieved 2008-01-16.

बाहरी संबंध

• NIST Dictionary of Algorithms and Data Structures: Turing reduction
• University of Cambridge, Andrew Pitts, Tobias Kohn: Computation Theory
• Prof. Jean Gallier’s Homepage