संभाव्य ट्यूरिंग मशीन

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

संक्रमणों के लिए समान संभावनाओं के मामले में, संभाव्य ट्यूरिंग मशीनों को नियतात्मक ट्यूरिंग मशीनों के रूप में परिभाषित किया जा सकता है, जिसमें एक अतिरिक्त लेखन निर्देश होता है, जहां लिखने का मूल्य ट्यूरिंग मशीन के वर्णमाला में समान वितरण (अलग) होता है (आम तौर पर, लिखने की एक समान संभावना होती है) टेप पर 1 या 0)। एक अन्य सामान्य सुधार बस एक नियतात्मक ट्यूरिंग मशीन है जिसमें यादृच्छिक बिट्स से भरा एक अतिरिक्त टेप होता है जिसे रैंडम टेप कहा जाता है।

एक कंप्यूटर जितना गणना का एक और मॉडल है जो स्वाभाविक रूप से संभाव्य है।

विवरण

एक संभाव्य ट्यूरिंग मशीन एक प्रकार की गैर-नियतात्मक ट्यूरिंग मशीन है जिसमें प्रत्येक गैर-नियतात्मक कदम एक सिक्का-फ्लिप होता है, अर्थात, प्रत्येक चरण में दो संभावित अगली चालें होती हैं और ट्यूरिंग मशीन संभावित रूप से चुनती है कि कौन सी चाल चलनी है।

औपचारिक परिभाषा

एक संभाव्य ट्यूरिंग मशीन को औपचारिक रूप से 7-टुपल के रूप में परिभाषित किया जा सकता है $M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})$, कहाँ

• $Q$ राज्यों का एक सीमित समूह है
• $\Sigma$ इनपुट वर्णमाला है
• $\Gamma$ एक टेप वर्णमाला है, जिसमें रिक्त प्रतीक # शामिल है
• $q_{0}\in Q$ प्रारंभिक अवस्था है
• $A\subseteq Q$ (अंतिम) राज्यों को स्वीकार करने का सेट है
• $\delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ पहला संभाव्य संक्रमण फलन है। $L$ ट्यूरिंग मशीन के टेप पर बायीं ओर एक सेल की गति है और $R$ दाईं ओर एक कोशिका एक आंदोलन है।
• $\delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ दूसरा संभाव्य संक्रमण फलन है।

प्रत्येक चरण पर, ट्यूरिंग मशीन संभावित रूप से या तो संक्रमण फ़ंक्शन लागू करती है $\delta _{1}$ या संक्रमण फ़ंक्शन $\delta _{2}$. यह चुनाव सभी पूर्व विकल्पों से स्वतंत्र रूप से किया गया है। इस तरह, गणना के प्रत्येक चरण में एक संक्रमण फ़ंक्शन का चयन करने की प्रक्रिया एक सिक्के के उछाल के समान होती है।

प्रत्येक चरण पर संक्रमण फ़ंक्शन का संभाव्य चयन ट्यूरिंग मशीन में त्रुटि उत्पन्न करता है; अर्थात्, जिन स्ट्रिंग्स को ट्यूरिंग मशीन को स्वीकार करना है, उन्हें कुछ अवसरों पर अस्वीकार किया जा सकता है और जिन स्ट्रिंग्स को ट्यूरिंग मशीन को अस्वीकार करना है, उन्हें कुछ अवसरों पर स्वीकार किया जा सकता है। इसे समायोजित करने के लिए, एक भाषा $L$ कहा जाता है कि इसे त्रुटि संभावना से पहचाना जाता है $\epsilon$एक संभाव्य ट्यूरिंग मशीन द्वारा $M$ अगर:

1. एक स्ट्रिंग $w$ में $L$ इसका आशय है ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$
2. एक स्ट्रिंग $w$ अंदर नही $L$ इसका आशय है ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$

जटिलता वर्ग

Unsolved problem in computer science:

Is P = BPP ?

(more unsolved problems in computer science)

संभाव्य सिक्का उछाल के उपयोग से उत्पन्न त्रुटि के परिणामस्वरूप, संभाव्य ट्यूरिंग मशीन द्वारा एक स्ट्रिंग की स्वीकृति की धारणा को विभिन्न तरीकों से परिभाषित किया जा सकता है। ऐसी ही एक धारणा जिसमें कई महत्वपूर्ण जटिलता वर्ग शामिल हैं, 1/3 की त्रुटि संभावना की अनुमति दे रही है। उदाहरण के लिए, जटिलता वर्ग बाउंडेड-त्रुटि संभाव्य बहुपद को 1/3 की त्रुटि संभावना के साथ बहुपद समय में संभाव्य ट्यूरिंग मशीन द्वारा मान्यता प्राप्त भाषाओं के वर्ग के रूप में परिभाषित किया गया है। स्वीकृति की इस धारणा का उपयोग करके परिभाषित एक अन्य वर्ग बीपीएल (जटिलता) है, जो बीपीपी के समान है लेकिन अतिरिक्त प्रतिबंध लगाता है कि भाषाओं को लॉगरिदमिक विकास स्थान जटिलता में हल करने योग्य होना चाहिए।

स्वीकृति की अन्य परिभाषाओं से उत्पन्न जटिलता वर्गों में आरपी (जटिलता), सह-आरपी, और जेडपीपी (जटिलता) शामिल हैं। यदि मशीन बहुपदी समय फलन बजाय लघुगणकीय स्थान तक सीमित है, तो अनुरूप आरएल (जटिलता), सह-आरएल, और जेडपीएल (जटिलता) जटिलता वर्ग प्राप्त होते हैं। दोनों प्रतिबंधों को लागू करने से, यादृच्छिक लघुगणक-अंतरिक्ष बहुपद-समय, सह-आरएलपी, बीपीएलपी और जेडपीएलपी प्राप्त होते हैं।

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

जटिलता सिद्धांत के केंद्रीय प्रश्नों में से एक यह है कि क्या यादृच्छिकता शक्ति जोड़ती है; अर्थात्, क्या ऐसी कोई समस्या है जिसे बहुपद समय में संभाव्य ट्यूरिंग मशीन द्वारा हल किया जा सकता है लेकिन नियतात्मक ट्यूरिंग मशीन द्वारा नहीं? या क्या नियतात्मक ट्यूरिंग मशीनें अधिकतम बहुपद मंदी के साथ सभी संभाव्य ट्यूरिंग मशीनों का कुशलतापूर्वक अनुकरण कर सकती हैं? यह ज्ञात है कि पी ⊆ बीपीपी, चूंकि एक नियतात्मक ट्यूरिंग मशीन एक संभाव्य ट्यूरिंग मशीन का एक विशेष मामला है। हालाँकि, यह अनिश्चित है कि क्या (लेकिन व्यापक रूप से संदेह है कि) BPP ⊆ P, जिसका अर्थ है कि BPP = P। बहुपद समय के बजाय लॉग स्पेस के लिए वही प्रश्न (क्या L = BPLP है?) और भी अधिक व्यापक रूप से सत्य माना जाता है। दूसरी ओर, शक्ति यादृच्छिकता इंटरैक्टिव प्रूफ सिस्टम को देती है, साथ ही सरल एल्गोरिदम जो इसे बहुपद-समय प्राइमलिटी परीक्षण और लॉग-स्पेस ग्राफ कनेक्टिविटी परीक्षण जैसी कठिन समस्याओं के लिए बनाता है, सुझाव देता है कि यादृच्छिकता शक्ति जोड़ सकती है।

यह भी देखें

• यादृच्छिक एल्गोरिथ्म

संदर्भ

• Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 123–142. ISBN 978-0-521-42426-4.
• Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). USA: Thomson Course Technology. pp. 368–380. ISBN 978-0-534-95097-2.

बाहरी संबंध

• NIST website on probabilistic Turing machines