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

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

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

एनुमेरेटर $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.