ओरेकल मशीन

Black box systems
Black box systems
System
	Black box · Oracle machine
Methods and techniques
	Black-box testing · Blackboxing
Related techniques
	Feed forward · Obfuscation · Pattern recognition · White box · White-box testing · Gray-box testing · System identification
Fundamentals
	A priori information · Control systems · Open systems · Operations research · Thermodynamic systems
	v; t; e;

कम्प्यूटेशनल जटिलता सिद्धांत और कम्प्यूटिबिलिटी सिद्धांत में, एक ओरेकल मशीन एक अमूर्त मशीन है जिसका उपयोग निर्णय समस्या ओं का अध्ययन करने के लिए किया जाता है।इसे एक ब्लैक बॉक्स के साथ ट्यूरिंग मशीन के रूप में कल्पना की जा सकती है, जिसे एक ओरेकल कहा जाता है, जो एक ऑपरेशन में कुछ समस्याओं को हल करने में सक्षम है।समस्या किसी भी जटिलता वर्ग की हो सकती है।यहां तक कि अवांछनीय समस्याएं, जैसे कि रुकने की समस्या का उपयोग किया जा सकता है।

oracles

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

एक निर्णय समस्या को प्राकृतिक संख्याओं (या तार) के सेट के रूप में दर्शाया जाता है।समस्या का एक उदाहरण एक मनमाना प्राकृतिक संख्या (या स्ट्रिंग) है।उदाहरण का समाधान हां है यदि संख्या (स्ट्रिंग) सेट में है, और अन्यथा नहीं।
एक फ़ंक्शन समस्या को प्राकृतिक संख्याओं (या स्ट्रिंग्स) से प्राकृतिक संख्याओं (या स्ट्रिंग्स) तक एक फ़ंक्शन f द्वारा दर्शाया जाता है।समस्या का एक उदाहरण एक इनपुट x f के लिए है।समाधान मूल्य f ( x ) है।

एक ओरेकल मशीन एक ट्यूरिंग मशीन के सभी सामान्य संचालन का प्रदर्शन कर सकती है, और ओरेकल को उस ओरेकल के लिए कम्प्यूटेशनल समस्या के किसी भी उदाहरण का समाधान प्राप्त करने के लिए भी क्वेरी कर सकती है।उदाहरण के लिए, यदि समस्या प्राकृतिक संख्याओं के सेट के सेट के लिए एक निर्णय समस्या है, तो ओरेकल मशीन एक प्राकृतिक संख्या के साथ ओरेकल की आपूर्ति करती है, और ओरेकल हां या ना के साथ प्रतिक्रिया करता है कि क्या यह संख्या एक तत्व है ए।

परिभाषाएँ

ओरेकल ट्यूरिंग मशीनों की कई समान परिभाषाएँ हैं, जैसा कि नीचे चर्चा की गई है।यहां प्रस्तुत किया गया एक वैन मेल्केबेक (2000: 43) से है।

एक ट्यूरिंग मशीन की तरह एक ओरेकल मशीन में शामिल हैं:

एक कार्य टेप: शुरुआत या अंत के बिना कोशिकाओं का एक अनुक्रम, जिनमें से प्रत्येक में एक बी (रिक्त के लिए) या टेप वर्णमाला से एक प्रतीक हो सकता है;
एक रीड/राइट हेड, जो वर्क टेप की एक ही सेल पर टिकी हुई है और वहां डेटा पढ़ सकती है, नया डेटा लिख सकती है, और टेप के साथ अपनी स्थिति को बढ़ा सकती है या बढ़ा सकती है;
एक नियंत्रण तंत्र, जो राज्यों की एक परिमित संख्या में से एक हो सकता है, और जो वर्तमान स्थिति और पढ़े जा रहे डेटा के आधार पर विभिन्न क्रियाओं (डेटा पढ़ना, डेटा लिखना, नियंत्रण तंत्र को स्थानांतरित करना, और बदलते राज्यों को स्थानांतरित करना) करेगा।

इन घटकों के अलावा, एक ओरेकल मशीन में भी शामिल है:

एक ओरेकल टेप, जो काम टेप से अलग एक अर्ध-अनंत टेप है।ओरेकल टेप के लिए वर्णमाला कार्य टेप के लिए वर्णमाला से अलग हो सकती है।
एक ओरेकल हेड, जो पढ़ने/लिखने वाले सिर की तरह, ओरेकल टेप पढ़ने और लिखने के प्रतीकों के साथ बाएं या दाएं स्थानांतरित कर सकता है;
दो विशेष राज्य: आस्क राज्य और प्रतिक्रिया राज्य।

समय -समय पर, ओरेकल मशीन आस्क स्टेट में प्रवेश कर सकती है।जब ऐसा होता है, तो निम्नलिखित क्रियाएं एक ही कम्प्यूटेशनल चरण में की जाती हैं:

ओरेकल टेप की सामग्री को ओरेकल की कम्प्यूटेशनल समस्या के उदाहरण के रूप में देखा जाता है;
ओरेकल से परामर्श किया जाता है, और ओरेकल टेप की सामग्री को समस्या के उस उदाहरण के समाधान के साथ बदल दिया जाता है;
ओरेकल हेड को ओरेकल टेप पर पहले वर्ग में ले जाया जाता है;
ओरेकल मशीन की स्थिति को प्रतिक्रिया में बदल दिया जाता है।

आस्क स्टेट में बदलने का प्रभाव इस प्रकार प्राप्त करना है, एक ही कदम में, समस्या उदाहरण का एक समाधान जो ओरेकल टेप पर लिखा गया है।

वैकल्पिक परिभाषाएँ

ऊपर प्रस्तुत की गई कई वैकल्पिक परिभाषाएँ हैं।इनमें से कई उस मामले के लिए विशेष हैं जहां ओरेकल एक निर्णय समस्या को हल करता है।इस मामले में:

कुछ परिभाषाएँ, Oracle टेप का उत्तर लिखने के बजाय, दो विशेष राज्य हैं हां और ASK राज्य के अलावा नहीं।जब ओरेकल से परामर्श किया जाता है, तो अगले राज्य को हां होने के लिए चुना जाता है यदि ओरेकल टेप की सामग्री ओरेकल सेट में होती है, और यदि सामग्री ओरेकल सेट में नहीं होती है तो नहीं चुना जाता है (अडाची 1990: 111)।
कुछ परिभाषाएं अलग ओरेकल टेप से बचती हैं।जब ओरेकल राज्य दर्ज किया जाता है, तो एक टेप प्रतीक निर्दिष्ट होता है।Oracle को उस समय की संख्या के साथ queried किया जाता है जब यह टेप प्रतीक कार्य टेप पर दिखाई देता है।यदि वह संख्या ओरेकल सेट में है, तो अगला राज्य हां राज्य है;यदि यह नहीं है, तो अगला राज्य कोई राज्य नहीं है (रोजर्स 1967: 129)।
एक अन्य वैकल्पिक परिभाषा ओरेकल टेप को केवल-पढ़ती है, और पूरी तरह से पूछ और प्रतिक्रिया राज्यों को समाप्त करती है।मशीन शुरू होने से पहले, ओरेकल सेट का संकेतक फ़ंक्शन ओरेकल टेप पर प्रतीकों 0 और 1 का उपयोग करके लिखा गया है। मशीन फिर ओरेकल को ओरेकल टेप पर सही वर्ग को स्कैन करके और वहां स्थित मूल्य को पढ़कर ओरेकल को क्वेरी करने में सक्षम है(सोरे 1987: 47, रोजर्स 1967: 130)।

ये परिभाषाएँ ट्यूरिंग कम्प्यूटिबिलिटी के दृष्टिकोण से बराबर हैं: एक फ़ंक्शन इन सभी परिभाषाओं के तहत किसी दिए गए ओरेकल से ओरेकल-कम्प्यूटेबल है, अगर यह उनमें से किसी के तहत ओरेकल-कंप्यूप्टेबल है।परिभाषाएँ समकक्ष नहीं हैं, हालांकि, कम्प्यूटेशनल जटिलता के दृष्टिकोण से।एक परिभाषा जैसे कि वैन मेल्केबेक द्वारा एक ओरेकल टेप का उपयोग करके, जिसकी अपनी वर्णमाला हो सकती है, सामान्य रूप से आवश्यक है।

ओरेकल मशीनों की जटिलता वर्ग

एक भाषा एल के लिए एक ओरेकल के साथ क्लास ए में एक एल्गोरिथ्म द्वारा सॉल्वेबल निर्णय की समस्याओं की जटिलता वर्ग को कहा जाता है।उदाहरण के लिए, पी एक नियतात्मक समय में एक नियतात्मक ट्यूरिंग मशीन द्वारा बूलियन संतुष्टिदायक समस्या के लिए एक नियतात्मक ट्यूरिंग मशीन द्वारा समस्याओं का वर्ग है।संकेतन को निम्नलिखित परिभाषा का उपयोग करके भाषाओं B (या एक जटिलता वर्ग B) के एक सेट तक बढ़ाया जा सकता है:

A^{B}=\bigcup _{L\in B}A^{L}

जब एक भाषा l कुछ कक्षा B के लिए पूर्ण (जटिलता) है, तो ए बशर्ते कि A में मशीनें कक्षा B की पूर्णता परिभाषा में उपयोग की जाने वाली कटौती को निष्पादित कर सकती हैं।हालाँकि, अगर a = dlogtime, तो a^Sat बराबर नहीं हो सकता है।(ध्यान दें कि की परिभाषा $A^{B}$ ऊपर दिया गया पूरी तरह से मानक नहीं है।कुछ संदर्भों में, जैसे कि समय पदानुक्रम प्रमेय और अंतरिक्ष पदानुक्रम प्रमेय का प्रमाण, यह मान लेना अधिक उपयोगी है कि अमूर्त मशीन को परिभाषित करना वर्ग $A$ केवल एक भाषा के लिए एक ही ओरेकल तक पहुंच है।इस संदर्भ में, $A^{B}$ यदि जटिलता वर्ग है तो परिभाषित नहीं किया गया है $B$ उपलब्ध कटौती के संबंध में कोई पूरी समस्या नहीं है $A$ ।)

यह समझा जाता है कि , लेकिन क्या एनपी का सवाल है^{एनपी , पी और p समान रूप से समान रूप से अस्थायी हैं।यह माना जाता है कि वे अलग हैं, और यह बहुपद पदानुक्रम की परिभाषा की ओर जाता है।}

पी के बीच संबंधों पर विचार करके, ओरेकल मशीनें पी = एनपी समस्या के बीच संबंधों की जांच के लिए उपयोगी हैं एक और एनपी एक Oracle A. के लिए विशेष रूप से, यह दिखाया गया है कि भाषाएं मौजूद हैं a और b जैसे कि pए और पी (बेकर, गिल, और सोलोवे 1975)।तथ्य यह है कि p = np प्रश्न दोनों तरीकों को साक्ष्य के रूप में लिया जाता है कि इस प्रश्न का उत्तर देना मुश्किल है, क्योंकि एक प्रूफ तकनीक जो रिलेटिवाइज़ करती है (यानी, एक Oracle के अलावा अप्रभावित) p = np प्रश्न का उत्तर नहीं देगी।अधिकांश प्रूफ तकनीकें रिलेटिवाइज़ करती हैं।

कोई उस मामले पर विचार कर सकता है जहां एक ओरेकल को सभी संभव oracles (एक अनंत सेट) में से बेतरतीब ढंग से चुना जाता है।यह इस मामले में दिखाया गया है, कि संभावना 1, पी के साथ एक (बेनेट और गिल 1981)।जब एक प्रश्न लगभग सभी oracles के लिए सच होता है, तो यह एक यादृच्छिक ओरेकल के लिए सच कहा जाता है।शब्दावली की यह पसंद इस तथ्य से उचित है कि यादृच्छिक oracles केवल संभावना 0 या 1 के साथ एक कथन का समर्थन करते हैं।(यह कोलमोगोरोव के शून्य -एक कानून से निम्नानुसार है।) यह केवल कमजोर सबूत है कि पी एंड ने; एनपी, क्योंकि एक बयान एक यादृच्छिक ओरेकल के लिए सच हो सकता है लेकिन साधारण ट्यूरिंग मशीनों के लिए गलत हो सकता है;उदाहरण के लिए, आईपी एक यादृच्छिक ओरेकल ए लेकिन आईपी (जटिलता) = PSPACE (चांग एट अल।, 1994) के लिए एक ।

oracles और रुकने की समस्याएं

रुकने की समस्या के लिए एक ओरेकल के साथ एक मशीन यह निर्धारित कर सकती है कि क्या विशेष ट्यूरिंग मशीनें विशेष इनपुट पर रोक देंगी, लेकिन यह सामान्य रूप से यह निर्धारित नहीं कर सकता है कि क्या मशीनें खुद के बराबर रुक जाएंगी।यह मशीनों का एक पदानुक्रम बनाता है, प्रत्येक में अधिक शक्तिशाली रुकने वाले ओरेकल और एक कठिन रुकने की समस्या होती है। मशीनों के इस पदानुक्रम का उपयोग अंकगणितीय पदानुक्रम (Börger 1989) को परिभाषित करने के लिए किया जा सकता है।

क्रिप्टोग्राफी के लिए आवेदन

क्रिप्टोग्राफी में, क्रिप्टोग्राफिक प्रोटोकॉल की सुरक्षा के लिए तर्क देने के लिए oracles का उपयोग किया जाता है जहां एक क्रिप्टोग्राफिक हैश फ़ंक्शन का उपयोग किया जाता है।प्रोटोकॉल के लिए एक सिद्ध सुरक्षा उस मामले में दी जाती है, जहां हैश फ़ंक्शन के बजाय, एक यादृच्छिक ओरेकल प्रत्येक क्वेरी को यादृच्छिक रूप से लेकिन लगातार उत्तर देता है;ओरेकल को हमलावर सहित सभी पक्षों के लिए उपलब्ध माना जाता है, जैसा कि हैश फ़ंक्शन है।इस तरह के प्रमाण से पता चलता है कि जब तक हमलावर सुरक्षा में कमी के दिल में कठिन समस्या को हल नहीं करता है, तब तक उन्हें प्रोटोकॉल को तोड़ने के लिए हैश फ़ंक्शन की कुछ दिलचस्प संपत्ति का उपयोग करना होगा;वे हैश फ़ंक्शन को एक ब्लैक बॉक्स (यानी, एक यादृच्छिक ओरेकल के रूप में) के रूप में नहीं मान सकते।

यह भी देखें

संदर्भ

Akeo Adachi, Foundations of computation theory, Ohmsha, 1990.
T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
C. H. Bennett, J. Gill. Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1. SIAM Journal on Computing, 10(1): 96-113 (1981)
Egon Börger. "Computability, Complexity, Logic". North-Holland, 1989.
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, Pankaj Rohatgi. The Random Oracle Hypothesis is False. Journal of Computer and System Sciences, volume 49, issue 1, pp. 24–39. August 1994. ISSN 0022-0000. http://citeseer.ist.psu.edu/282397.html
Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Turing's paper is in this volume. Papers include those by Gödel, Church, Rosser, Kleene, and Post.
Christos Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339–343.
Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
Michael Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997. ISBN 0-534-94728-X. Section 9.2: Relativization, pp. 318–321.
Robert I. Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer, 1987.
Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
Dieter van Melkebeek, Randomness and Completeness in Computational Complexity, Lecture Notes in Computer Science 1950, Springer, 2000.

श्रेणी: कम्प्यूटिबिलिटी थ्योरी श्रेणी: ट्यूरिंग मशीन *