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

गणितीयता सिद्धांत में, एक निर्णय समस्या $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$