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

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

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

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

मजबूत कटौती

ट्यूरिंग रिड्यूसबिलिटी की तुलना में कटौती को मजबूत बनाने के दो सामान्य तरीके हैं। पहला तरीका ऑरैकल प्रश्नों की संख्या और तरीके को सीमित करना है।

• तय करना $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