ट्यूरिंग न्यूनन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(13 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Concept in computability theory}}
{{Short description|Concept in computability theory}}
कम्प्यूटेबिलिटी [[संगणनीयता सिद्धांत]], एक [[निर्णय समस्या]] से एक ट्यूरिंग कमी <math>A</math> निर्णय समस्या के लिए <math>B</math> एक [[ओरेकल मशीन]] है जो समस्या का निर्णय करती है <math>A</math> के लिए एक ओरेकल दिया <math>B</math> (रोजर्स 1967, सोरे 1987)। इसे एक [[कलन विधि]] के रूप में समझा जा सकता है जिसका उपयोग हल करने के लिए किया जा सकता है <math>A</math> यदि उसके पास बी को हल करने के लिए एक उपनेमका उपलब्ध था। इस अवधारणा को कार्य समस्याओं पर भी लागू किया जा सकता है।
[[गणितीयता सिद्धांत]] में, एक [[निर्णय समस्या]] <math>A</math> से एक निर्णय समस्या <math>B</math> की '''त्यौरिंग संक्षेपण''' एक [[ऑरेकल मशीन]] होती है जो <math>B</math> के लिए एक ऑरेकल के द्वारा समस्या <math>A</math> का निर्णय करती है (रोजर्स 1967, सोरे 1987)। इसे एक ऐसे [[एल्गोरिदम]] के रूप में समझा जा सकता है जो समस्या <math>B</math>  को हल करने के लिए उपलब्ध होने पर समस्या <math>A</math> को हल करने के लिए उपयोग किया जा सकता है। इस संक्षेपण को [[फ़ंक्शन समस्याओं]] पर भी समानांतर लागू किया जा सकता है।  


यदि <math>A</math> से <math>B</math> तक एक ट्यूरिंग रिडक्शन मौजूद है, तो <math>B</math>{{efn|It is possible that ''B'' is an [[undecidable problem]] for which no algorithm exists.}} के लिए प्रत्येक एल्गोरिथ्म का उपयोग <math>A</math> के लिए एक एल्गोरिथ्म का उत्पादन करने के लिए किया जा सकता है, प्रत्येक स्थान पर <math>B</math>  के लिए एल्गोरिथ्म डालकर जहां ओरेकल मशीन कंप्यूटिंग A, B के लिए ओरेकल से पूछताछ करता है। हालांकि, क्योंकि ओरेकल मशीन बड़ी संख्या में ओरेकल से पूछताछ कर सकती है, परिणामी एल्गोरिथ्म को <math>B</math> के लिए एल्गोरिथ्म या ओरेकल मशीन कंप्यूटिंग की तुलना में एसिम्प्टोटिक रूप से अधिक समय की आवश्यकता हो सकती है। एक ट्यूरिंग रिडक्शन जिसमें ओरेकल मशीन बहुपद समय में चलती है, उसे [[कुक रिडक्शन]] के रूप में जाना जाता है।
यदि <math>A</math> से <math>B</math> की त्यौरिंग संक्षेपण मौजूद होता है, तो <math>B</math>{{efn|It is possible that ''B'' is an [[undecidable problem]] for which no algorithm exists.}} के लिए के लिए उपयोग होने वाले प्रत्येक [[एल्गोरिदम]] का उपयोग करके <math>A</math> के लिए एक एल्गोरिदम बनाया जा सकता है, जहां A को त्यौरिंग संक्षेपण करने वाली ऑरेकल मशीन B के लिए ऑरेकल से पूछताछ करती है।हालांकि, क्योंकि ऑरेकल मशीन ऑरेकल की बड़ी संख्या में पूछताछ कर सकती है, इसलिए परिणामी एल्गोरिदम <math>B</math> या <math>A</math> के एल्गोरिदम या ऑरेकल मशीन के कंप्यूटिंग से असिम्प्टोटिक रूप से अधिक समय की आवश्यकता हो सकती है। पोलिनोमियल समय में ऑरेकल मशीन चलने वाला एक त्यौरिंग संक्षेपण को [[कुक संक्षेपण]] के रूप में जाना जाता है।


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


दो सेट दिए गए हैं <math>A,B \subseteq \mathbb{N}</math> प्राकृतिक संख्या, हम कहते हैं <math>A</math> ट्यूरिंग के लिए कम करने योग्य है <math>B</math> और लिखा
दो सेट दिए गए हैं <math>A,B \subseteq \mathbb{N}</math> प्राकृतिक संख्या, हम कहते हैं कि <math>A</math> ट्यूरिंग <math>B</math> तक रिड्यूसिबल है और लिखें
:<math>A \leq_T B</math>
अगर और केवल अगर एक ओरेकल मशीन है जो ओरेकल बी के साथ चलने पर ए के संकेतक फ़ंक्शन की गणना करती है। इस मामले में, हम यह भी कहते हैं कि ए 'बी-पुनरावर्ती' और 'बी-गणना योग्य' है।


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


हम कहते हैं <math>A</math> ट्यूरिंग के बराबर है <math>B</math> और लिखा <math>A \equiv_T B\,</math> अगर दोनों <math>A \leq_T B</math> और <math>B \leq_T A.</math> ट्यूरिंग समतुल्य सेटों के [[तुल्यता वर्ग]]ों को [[ट्यूरिंग डिग्री]] कहा जाता है। एक सेट की ट्यूरिंग डिग्री <math>X</math> लिखा है <math>\textbf{deg}(X)</math>.
यदि एक [[ओरेकल मशीन]] है जो ओरेकल ''बी''  के साथ चलाई जाती हुई ''ए''  के [[संकेतक फ़ंक्शन]] की गणना करती है। इस स्थिति में, हम यह भी कहते हैं कि ''ए'' ''''''बी-''पुनरावर्ती'''<nowiki/>' और '<nowiki/>'''''बी'''''-'''गणना योग्य'''<nowiki/>' है।


एक सेट दिया <math>\mathcal{X} \subseteq \mathcal{P}(\mathbb{N})</math>, एक सेट <math>A \subseteq \mathbb{N}</math> ट्यूरिंग हार्ड के लिए कहा जाता है <math>\mathcal{X}</math> अगर <math>X \leq_T A</math> सभी के लिए <math>X \in \mathcal{X}</math>. अगर अतिरिक्त <math>A \in \mathcal{X}</math> तब <math>A</math> ट्यूरिंग के लिए पूर्ण कहा जाता है <math>\mathcal{X}</math>.
यदि एक ऑरेकल मशीन है जो बी के साथ चलाई जाती हुई एक आंशिक फ़ंक्शन की हिसाब कर सकती है जिसका डोमेन ए है, तो ''ए'' को '[[पुनरावर्ती गणना योग्य सेट]]' और ''''''बी'''''-'''कम्प्यूटेशनल इन्युमरेबल'''<nowiki/>' कहा जाता है।
 
हम कहते हैं <math>A</math> '''ट्यूरिंग के बराबर''' है <math>B</math> और लिखा <math>A \equiv_T B\,</math> अगर दोनों <math>A \leq_T B</math> और <math>B \leq_T A.</math> ट्यूरिंग समतुल्य सेटों के [[तुल्यता वर्ग]]ों को [[ट्यूरिंग डिग्री]] कहा जाता है। एक सेट की ट्यूरिंग डिग्री <math>X</math> लिखा है <math>\textbf{deg}(X)</math>.
 
एक सेट दिया <math>\mathcal{X} \subseteq \mathcal{P}(\mathbb{N})</math>, एक सेट <math>A \subseteq \mathbb{N}</math> ट्यूरिंग हार्ड के लिए कहा जाता है <math>\mathcal{X}</math> अगर <math>X \leq_T A</math> सभी के लिए <math>X \in \mathcal{X}</math>. अगर अतिरिक्त <math>A \in \mathcal{X}</math> तब <math>A</math> ट्यूरिंग के लिए पूर्ण कहा जाता है <math>\mathcal{X}</math>


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


== उदाहरण ==
== उदाहरण ==


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


* हर सेट अपने पूरक के बराबर ट्यूरिंग है।
* प्रत्येक सेट ट्यूरिंग के पूरक के बराबर है।
* हर गणनीय सेट हर दूसरे सेट के लिए ट्यूरिंग रिड्यूसिबल है। क्योंकि किसी भी गणन योग्य सेट की गणना बिना किसी ऑरेकल के की जा सकती है, इसकी गणना एक ऑरेकल मशीन द्वारा की जा सकती है जो दिए गए ऑरेकल को अनदेखा करती है।
* प्रत्येक कम्प्यूटेबल सेट ट्यूरिंग प्रत्येक अन्य सेट के लिए रिड्यूसिबल है। क्योंकि किसी भी गणन योग्य सेट की गणना बिना किसी ऑरेकल के की जा सकती है, इसकी गणना एक ऑरेकल मशीन द्वारा की जा सकती है जो दिए गए ऑरेकल को अनदेखा करती है।
* रिश्ता <math>\leq_T</math> सकर्मक है: यदि <math>A \leq_T B</math> और <math>B \leq_T C</math> तब <math>A \leq_T C</math>. इसके अतिरिक्त, <math>A \leq_T A</math> प्रत्येक समुच्चय A के लिए मान्य है, और इस प्रकार संबंध <math>\leq_T</math> एक [[पूर्व आदेश]] है (यह आंशिक ऑर्डर नहीं है क्योंकि <math>A \leq_T B</math> और <math>B \leq_T A </math> जरूरी नहीं है <math>A = B</math>).
* रिश्ता <math>\leq_T</math> सकर्मक है: यदि <math>A \leq_T B</math> और <math>B \leq_T C</math> तब <math>A \leq_T C</math>. इसके अतिरिक्त, <math>A \leq_T A</math> प्रत्येक समुच्चय A के लिए मान्य है, और इस प्रकार संबंध <math>\leq_T</math> एक [[पूर्व आदेश]] है (यह आंशिक ऑर्डर नहीं है क्योंकि <math>A \leq_T B</math> और <math>B \leq_T A </math> जरूरी नहीं है <math>A = B</math>)
* सेट के जोड़े हैं <math>(A,B)</math> ऐसा है कि A, B के लिए ट्यूरिंग रिड्यूसिबल नहीं है और B, A के लिए ट्यूरिंग रिड्यूसिबल नहीं है <math>\leq_T</math> [[कुल आदेश]] नहीं है।
* सेट के जोड़े हैं <math>(A,B)</math> ऐसा है कि A, B के लिए ट्यूरिंग रिड्यूसिबल नहीं है और B, A के लिए ट्यूरिंग रिड्यूसिबल नहीं है <math>\leq_T</math> [[कुल आदेश]] नहीं है।
* नीचे सेट के अनंत घटते क्रम हैं <math>\leq_T</math>. इस प्रकार यह संबंध अच्छी तरह से स्थापित नहीं है।
* नीचे सेट के अनंत घटते क्रम हैं <math>\leq_T</math>. इस प्रकार यह संबंध [[अच्छी तरह]] से स्थापित नहीं है।
* हर सेट अपने स्वयं के [[ ट्यूरिंग कूदो ]] के लिए ट्यूरिंग रिड्यूसिबल है, लेकिन सेट का ट्यूरिंग जंप मूल सेट के लिए ट्यूरिंग रिड्यूसिबल नहीं है।
* हर सेट अपने स्वयं के [[ ट्यूरिंग कूदो ]] के लिए ट्यूरिंग रिड्यूसिबल है, लेकिन सेट का ट्यूरिंग जंप मूल सेट के लिए ट्यूरिंग रिड्यूसिबल नहीं है।


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


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


== मजबूत कटौती ==
== मजबूत कटौती ==


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


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


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


== कमजोर कटौती ==
== कमजोर कटौती ==


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


== यह भी देखें ==
== यह भी देखें ==
Line 102: Line 103:


{{Authority control}}
{{Authority control}}
[[Category: कमी (जटिलता)]] [[Category: एलन ट्यूरिंग]]
 


[[he:רדוקציה חישובית]]
[[he:רדוקציה חישובית]]


[[Category: Machine Translated Page]]
[[Category:Created On 31/05/2023]]
[[Category:Created On 31/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:एलन ट्यूरिंग]]
[[Category:कमी (जटिलता)]]

Latest revision as of 09:15, 30 June 2023

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

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

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

परिभाषा

दो सेट दिए गए हैं प्राकृतिक संख्या, हम कहते हैं कि ट्यूरिंग तक रिड्यूसिबल है और लिखें

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

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

हम कहते हैं ट्यूरिंग के बराबर है और लिखा अगर दोनों और ट्यूरिंग समतुल्य सेटों के तुल्यता वर्गों को ट्यूरिंग डिग्री कहा जाता है। एक सेट की ट्यूरिंग डिग्री लिखा है .

एक सेट दिया , एक सेट ट्यूरिंग हार्ड के लिए कहा जाता है अगर सभी के लिए . अगर अतिरिक्त तब ट्यूरिंग के लिए पूर्ण कहा जाता है

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

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

उदाहरण

यदि इनपुट मूल्यों के सेट को निरूपित करें जिसके लिए इंडेक्स ई के साथ ट्यूरिंग मशीन रुक जाती है। फिर सेट और ट्यूरिंग समतुल्य हैं (यहाँ एक प्रभावी युग्मन कार्य को दर्शाता है)। कमी दिखा रहा है इस तथ्य का उपयोग करके बनाया जा सकता है कि . एक जोड़ा दिया , एक नया सूचकांक Smn प्रमेय का उपयोग करके बनाया जा सकता हैmn प्रमेय ऐसा है कि कार्यक्रम द्वारा कोडित इसके इनपुट को अनदेखा करता है और केवल इनपुट एन पर इंडेक्स ई के साथ मशीन की गणना का अनुकरण करता है। विशेष रूप से, index या तो हर इनपुट पर रुकता है या बिना इनपुट के रुकता है। इस प्रकार सभी ई और एन के लिए रखती है। क्योंकि फ़ंक्शन i गणना योग्य है, यह दिखाता है . यहां प्रस्तुत कटौती न केवल ट्यूरिंग कटौती बल्कि कई-एक कटौती हैं, जिनकी चर्चा नीचे की गई है।

गुण

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

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

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

मजबूत कटौती

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

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

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

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

कमजोर कटौती

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

यह भी देखें

टिप्पणियाँ

  1. It is possible that B is an undecidable problem for which no algorithm exists.


संदर्भ

  • 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.


बाहरी संबंध