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

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

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

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

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

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

सबूत

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

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

1 के लिए i = 1,2,3,...
2 भागो $M$ इनपुट स्ट्रिंग के साथ $s_{1},s_{2},\dots ,s_{i}$ के लिए $i$-कदम
3 यदि कोई स्ट्रिंग स्वीकृत है तो उसे प्रिंट कर लें।

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

एक गणना योग्य भाषा ट्यूरिंग पहचानने योग्य है

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

संदर्भ

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