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

Latest revision as of 11:37, 14 August 2023

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

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

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

This computing article is a stub. You can help Wikipedia by expanding it.

@@ Line 1: / Line 1: @@
-{{Short description|Automata that lists elements of some given set}}गणनाकार एक [[ट्यूरिंग मशीन]] है जिसमें एक प्रिंटर लगा होता है। ट्यूरिंग मशीन स्ट्रिंग्स को प्रिंट करने के लिए उस प्रिंटर को आउटपुट डिवाइस के रूप में उपयोग कर सकती है। हर बार जब ट्यूरिंग मशीन सूची में एक स्ट्रिंग जोड़ना चाहती है, तो वह स्ट्रिंग को प्रिंटर को भेजती है। एन्यूमरेटर एक प्रकार का ट्यूरिंग मशीन प्रकार है और ट्यूरिंग मशीन के समकक्ष है।
+{{Short description|Automata that lists elements of some given set}}एनुमेरेटर [[ट्यूरिंग मशीन]] है जिसमें प्रिंटर लगा होता है। ट्यूरिंग मशीन स्ट्रिंग्स को प्रिंट करने के लिए उस प्रिंटर को आउटपुट डिवाइस के रूप में उपयोग कर सकती है। जब प्रत्येक ट्यूरिंग मशीन सूची में स्ट्रिंग जोड़ना चाहती है, तब वह स्ट्रिंग को प्रिंटर को भेजती है। '''एन्यूमरेटर''' प्रकार का ट्यूरिंग मशीन प्रकार है और जो ट्यूरिंग मशीन के समकक्ष होता है।
 ==औपचारिक परिभाषा==
-एक गणनाकार <math>E</math> इसे 2-टेप ट्यूरिंग मशीन ([[मल्टीटेप ट्यूरिंग मशीन]]) के रूप में परिभाषित किया जा सकता है <math> k=2 </math>) किसकी भाषा है <math>\empty</math>. शुरू में, <math>E</math> कोई इनपुट प्राप्त नहीं होता है, और सभी टेप खाली हैं (यानी, खाली प्रतीकों से भरे हुए हैं)। नव परिभाषित प्रतीक <math>\#\in \Gamma\land\#\notin \Sigma</math> वह परिसीमनक है जो किसी तत्व के अंत को चिह्नित करता है <math>S</math>. दूसरे टेप को प्रिंटर के रूप में माना जा सकता है, इस पर तारों को अलग किया जाता है <math>\#</math>. गणनाकार द्वारा गणना की गई भाषा <math>E</math> द्वारा चिह्नित <math>L(E)</math> दूसरे टेप (प्रिंटर) पर स्ट्रिंग्स के सेट के रूप में परिभाषित किया गया है।
+एनुमेरेटर <math>E
+                                             </math> को 2-टेप ट्यूरिंग मशीन (मल्टीटेप ट्यूरिंग मशीन जहां <math> k=2 </math>) के रूप में परिभाषित किया जा सकता है, जिसकी लैंग्वेज <math>\empty</math> है। प्रारंभ में, <math>E</math> को कोई इनपुट नहीं मिलता है, और सभी टेप खाली हैं (अथार्त, खाली प्रतीकों से भरे हुए हैं)। नया परिभाषित प्रतीक <math>\#\in \Gamma\land\#\notin \Sigma</math> वह सीमांकक है जो <math>S</math> के अवयव के अंत को चिह्नित करता है। दूसरे टेप को प्रिंटर के रूप में माना जा सकता है, इस पर स्ट्रिंग्स को <math>\#</math> द्वारा अलग किया जाता है। एनुमेरेटर ई द्वारा गणना की गई लैंग्वेज को <math>L(E)</math> द्वारा निरूपित करके दूसरे टेप (प्रिंटर) पर स्ट्रिंग के सेट के रूप में परिभाषित किया गया है।
-==प्रगणक और ट्यूरिंग मशीनों की समतुल्यता==
+==एनुमेरेटर और ट्यूरिंग मशीनों की समतुल्यता==
-एक सीमित वर्णमाला पर एक भाषा ट्यूरिंग पहचानने योग्य है यदि और केवल तभी इसे एक गणनाकर्ता द्वारा गिना जा सकता है। इससे पता चलता है कि ट्यूरिंग की पहचान योग्य भाषाएँ भी पुनरावर्ती रूप से गणना योग्य हैं।
+सीमित वर्णमाला पर लैंग्वेज ट्यूरिंग पहचानने योग्य है यदि यह केवल तभी इसे गणनाकर्ता द्वारा गिना जा सकता है। इससे पता चलता है कि ट्यूरिंग की पहचान योग्य लैंग्वेज भी पुनरावर्ती रूप से गणना योग्य हैं।
-सबूत
+प्रमाण
-एक ट्यूरिंग पहचानने योग्य भाषा की गणना एक गणनाकार द्वारा की जा सकती है
+ट्यूरिंग पहचानने योग्य लैंग्वेज की गणना एनुमेरेटर द्वारा की जा सकती है
-एक ट्यूरिंग मशीन पर विचार करें <math>M</math> और उसके द्वारा स्वीकृत भाषा हो <math>L(M)</math>. चूंकि इनपुट वर्णमाला पर सभी संभावित स्ट्रिंग्स का सेट <math>\Sigma</math> यानी क्लेन क्लोजर <math>\Sigma^{*}</math> एक गणनीय समुच्चय है, हम इसमें स्ट्रिंग्स की गणना इस प्रकार कर सकते हैं <math>s_{1},s_{2},\dots ,s_{i},</math> आदि। फिर प्रगणक भाषा की गणना करता है <math>L(M)</math> चरणों का पालन करेंगे:
+ट्यूरिंग मशीन <math>M</math> पर विचार करें और इसके द्वारा स्वीकृत लैंग्वेज <math>L(M)</math> है। चूंकि इनपुट वर्णमाला <math>\Sigma</math> पर सभी संभावित स्ट्रिंग्स का सेट अर्थात। क्लेन क्लोजर <math>\Sigma^{*}</math> गणनीय सेट है, हम इसमें स्ट्रिंग्स को <math>s_{1},s_{2},\dots ,s_{i},</math> आदि के रूप में गिन सकते हैं। फिर लैंग्वेज <math>L(M)</math> की गणना करने वाला एनुमेरेटर निम्नलिखित चरणों का पालन करेगा |
-के लिए i = 1,2,3,...
+'''for''' i = 1,2,3,...
-भागो <math>M</math> इनपुट स्ट्रिंग के साथ <math>s_{1}, s_{2}, \dots, s_{i}</math> के लिए <math>i</math>-कदम
+'''Run''' '''with input strings''' '''for''' -'''steps'''
-यदि कोई स्ट्रिंग स्वीकृत है तो उसे प्रिंट कर लें।
+If any string is accepted, then print it.
-अब प्रश्न यह आता है कि क्या भाषा में प्रत्येक तार <math>L(M)</math> हमारे द्वारा निर्मित प्रगणक द्वारा मुद्रित किया जाएगा। किसी भी स्ट्रिंग के लिए <math>w</math> भाषा में <math>L(M)</math> टीएम <math>M</math> सीमित संख्या में चरण चलेंगे (इसे रहने दें <math>k</math> के लिए <math>w</math>) इसे स्वीकार करना। फिर में <math>k</math>प्रगणक का -वाँ चरण <math>w</math> मुद्रित किया जाएगा. इस प्रकार गणनाकार प्रत्येक स्ट्रिंग को प्रिंट करेगा <math>M</math> पहचानता है लेकिन एक ही स्ट्रिंग को कई बार मुद्रित किया जा सकता है।
+अब प्रश्न यह आता है कि क्या लैंग्वेज <math>L(M)</math> की प्रत्येक स्ट्रिंग हमारे द्वारा निर्मित एन्यूमरेटर द्वारा प्रिंटिंग की जाएगी। लैंग्वेज <math>L(M)</math> में किसी भी स्ट्रिंग <math>w</math> के लिए TM <math>M</math> इसे स्वीकार करने के लिए सीमित संख्या में चरण चलाया जाट हैं (इसे <math>w</math> के लिए <math>k</math> होने दें)। फिर एन्यूमरेटर के <math>k</math>-वें चरण में <math>w</math> प्रिंट किया जाएगा। इस प्रकार एनुमेरेटर <math>M</math> द्वारा पहचानी गई प्रत्येक स्ट्रिंग को प्रिंट करेगा किन्तु स्ट्रिंग को अनेक बार प्रिंटिंग किया जा सकता है।
-एक गणना योग्य भाषा ट्यूरिंग पहचानने योग्य है
+गणना योग्य लैंग्वेज ट्यूरिंग पहचानने योग्य है
-ट्यूरिंग मशीन का निर्माण करना बहुत आसान है <math>M</math> जो असंख्य भाषा को पहचानता है <math>L</math>. हमारे पास दो टेप हो सकते हैं. एक टेप पर हम इनपुट स्ट्रिंग लेते हैं और दूसरे टेप पर, हम एक के बाद एक भाषा में स्ट्रिंग्स की गणना करने के लिए एन्यूमरेटर चलाते हैं। एक बार जब एक स्ट्रिंग दूसरे टेप में मुद्रित हो जाती है तो हम इसकी तुलना पहले टेप के इनपुट से करते हैं। यदि यह मेल खाता है, तो हम इनपुट स्वीकार करते हैं, अन्यथा अस्वीकार करते हैं।
+ट्यूरिंग मशीन <math>M</math> का निर्माण करना बहुत सरल है जो गणना योग्य लैंग्वेज <math>L</math> को पहचानती है। हमारे समीप दो टेप हो सकते हैं। टेप पर हम इनपुट स्ट्रिंग लेते हैं और दूसरे टेप पर, हम इसके पश्चात् लैंग्वेज में स्ट्रिंग्स की गणना करने के लिए एन्यूमरेटर चलाते हैं। जब स्ट्रिंग दूसरे टेप में प्रिंटिंग हो जाती है तब हम इसकी तुलना पहले टेप के इनपुट से करते हैं। यदि यह मेल खाता है, तब हम इनपुट स्वीकार करते हैं, अन्यथा अस्वीकार करते हैं।
-== संदर्भ ==
+== संदर्भ                                                        ==
 {{cite book |last=Sipser |first=Michael |title=Introduction to the Theory of Computation - International Edition |year=2012 |isbn=978-1-133-18781-3}}
-[[Category: कम्प्यूटेबिलिटी सिद्धांत]] [[Category: गणना का सिद्धांत]]
 {{compu-stub}}
+[[Category:All stub articles]]
+[[Category:Computing stubs]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 25/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:कम्प्यूटेबिलिटी सिद्धांत]]
+[[Category:गणना का सिद्धांत]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 11:37, 14 August 2023

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

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 11:37, 14 August 2023

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

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories