प्रगणक (कंप्यूटर विज्ञान)

गणनाकार एक ट्यूरिंग मशीन है जिसमें एक प्रिंटर लगा होता है। ट्यूरिंग मशीन स्ट्रिंग्स को प्रिंट करने के लिए उस प्रिंटर को आउटपुट डिवाइस के रूप में उपयोग कर सकती है। हर बार जब ट्यूरिंग मशीन सूची में एक स्ट्रिंग जोड़ना चाहती है, तो वह स्ट्रिंग को प्रिंटर को भेजती है। एन्यूमरेटर एक प्रकार का ट्यूरिंग मशीन प्रकार है और जो ट्यूरिंग मशीन के समकक्ष है।

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

एक प्रगणक $E$ को 2-टेप ट्यूरिंग मशीन (मल्टीटेप ट्यूरिंग मशीन जहां $k=2$) के रूप में परिभाषित किया जा सकता है, जिसकी लैंग्वेज $\emptyset$ है। प्रारंभ में, $E$ को कोई इनपुट नहीं मिलता है, और सभी टेप खाली हैं (अथार्त, खाली प्रतीकों से भरे हुए हैं)। नया परिभाषित प्रतीक $\#\in \Gamma \land \#\notin \Sigma$ वह सीमांकक है जो $S$ के एक तत्व के अंत को चिह्नित करता है। दूसरे टेप को प्रिंटर के रूप में माना जा सकता है, इस पर स्ट्रिंग्स को $\#$ द्वारा अलग किया जाता है। प्रगणक ई द्वारा गणना की गई लैंग्वेज को $L(E)$ द्वारा निरूपित करके दूसरे टेप (प्रिंटर) पर स्ट्रिंग के सेट के रूप में परिभाषित किया गया है।

प्रगणक और ट्यूरिंग मशीनों की समतुल्यता

एक सीमित वर्णमाला पर एक लैंग्वेज ट्यूरिंग पहचानने योग्य है यदि और केवल तभी इसे एक गणनाकर्ता द्वारा गिना जा सकता है। इससे पता चलता है कि ट्यूरिंग की पहचान योग्य लैंग्वेज भी पुनरावर्ती रूप से गणना योग्य हैं।

प्रमाण

एक ट्यूरिंग पहचानने योग्य लैंग्वेज की गणना एक गणनाकार द्वारा की जा सकती है

एक ट्यूरिंग मशीन $M$ पर विचार करें और इसके द्वारा स्वीकृत लैंग्वेज $L(M)$ है। चूंकि इनपुट वर्णमाला $\Sigma$ पर सभी संभावित स्ट्रिंग्स का सेट यानी। क्लेन क्लोजर $\Sigma ^{*}$ एक गणनीय सेट है, हम इसमें स्ट्रिंग्स को $s_{1},s_{2},\dots ,s_{i},$ आदि के रूप में गिन सकते हैं। फिर लैंग्वेज $L(M)$ की गणना करने वाला प्रगणक निम्नलिखित चरणों का पालन करेगा:

1 for i = 1,2,3,...
2 Run  with input strings  for -steps
3 If any string is accepted, then print it. 

अब प्रश्न यह आता है कि क्या लैंग्वेज $L(M)$ की प्रत्येक स्ट्रिंग हमारे द्वारा निर्मित एन्यूमरेटर द्वारा मुद्रित की जाएगी। लैंग्वेज $L(M)$ में किसी भी स्ट्रिंग $w$ के लिए TM $M$ इसे स्वीकार करने के लिए सीमित संख्या में चरण चलाएगा (इसे $w$ के लिए $k$ होने दें)। फिर एन्यूमरेटर के $k$-वें चरण में $w$ प्रिंट किया जाएगा। इस प्रकार गणनाकार $M$ द्वारा पहचानी गई प्रत्येक स्ट्रिंग को प्रिंट करेगा लेकिन एक स्ट्रिंग को कई बार मुद्रित किया जा सकता है।

एक गणना योग्य लैंग्वेज ट्यूरिंग पहचानने योग्य है

ट्यूरिंग मशीन $M$ का निर्माण करना बहुत सरल है जो गणना योग्य लैंग्वेज $L$ को पहचानती है। हमारे पास दो टेप हो सकते हैं। एक टेप पर हम इनपुट स्ट्रिंग लेते हैं और दूसरे टेप पर, हम एक के बाद एक लैंग्वेज में स्ट्रिंग्स की गणना करने के लिए एन्यूमरेटर चलाते हैं। एक बार जब एक स्ट्रिंग दूसरे टेप में मुद्रित हो जाती है तो हम इसकी तुलना पहले टेप के इनपुट से करते हैं। यदि यह मेल खाता है, तो हम इनपुट स्वीकार करते हैं, अन्यथा अस्वीकार करते हैं।

संदर्भ

Sipser, Michael (2012). Introduction to the Theory of Computation - International Edition. ISBN 978-1-133-18781-3.