मल्टीटेप ट्यूरिंग मशीन: Difference between revisions

Revision as of 18:44, 6 July 2023

मल्टी-टेप ट्यूरिंग मशीन ट्यूरिंग मशीन का एक प्रकार है जो कई टेपों का उपयोग करती है। पढ़ने और लिखने के लिए प्रत्येक टेप का अपना सिर होता है। प्रारंभ में, निविष्ट टेप 1 पर दिखाई देता है, और अन्य खाली शुरू होते हैं।^[1] यह मॉडल सहज रूप से एकल-टेप मॉडल की तुलना में बहुत अधिक शक्तिशाली लगता है, लेकिन किसी भी मल्टी-टेप मशीन - चाहे कितने भी टेप हों - एकल-टेप मशीन द्वारा केवल द्विघात फलन का अधिक गणना समय का उपयोग करके अनुकरण किया जा सकता है।^[2] इस प्रकार, मल्टी-टेप मशीनें एकल-टेप मशीनों की तुलना में किसी भी अधिक फलन की गणना नहीं कर सकती हैं,^[3] और कोई भी मजबूत जटिलता वर्ग (जैसे बहुपद समय) एकल-टेप और मल्टी-टेप मशीनों के बीच परिवर्तन से प्रभावित नहीं होता है

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

$k$ -टेप ट्यूरिंग मशीन को औपचारिक रूप से 7-टपल के रूप में परिभाषित किया जा सकता है $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ ट्यूरिंग मशीन के संकतन का अनुसरण करते हुए:

$\Gamma$ टेप वर्णमाला प्रतीकों का एक सीमित, गैर-रिक्त सेट है;
$b\in \Gamma$ रिक्त प्रतीक है (गणना के दौरान किसी भी चरण में टेप पर अनंत बार आने वाला एकमात्र प्रतीक);
$\Sigma \subseteq \Gamma \setminus \{b\}$ निविष्ट प्रतीकों का सेट है, यानी, प्रारंभिक टेप सामग्री में प्रदर्शित होने की अनुमति वाले प्रतीकों का सेट;
$Q$ अवस्थायों का एक सीमित, गैर-रिक्त सेट है;
$q_{0}\in Q$ प्रारंभिक अवस्था है;
$F\subseteq Q$ अंतिम अवस्थाओं या स्वीकार करने वाली अवस्थाओं का समूह है। कहा जाता है कि प्रारंभिक टेप सामग्री को स्वीकार कर लिया गया है $M$ यदि यह अंततः एक स्थिति में रुक जाता है $F$ .
$\delta :(Q\setminus F)\times \Gamma ^{k}\to Q\times \Gamma ^{k}\times \{L,R\}^{k}$ एक आंशिक फलन है जिसे पारगमन फलन कहा जाता है, जहां L बाईं शिफ्ट है, R दाईं शिफ्ट है।

$k$ -टेप ट्यूरिंग मशीन $M$ निम्नानुसार गणना करता है। शुरू में, $M$ उसका निविष्ट प्राप्त करता है $w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}$ सबसे बाईं ओर $n$ पहले टेप की स्थिति, पहले टेप के साथ-साथ अन्य टेपों का शेष भाग रिक्त है (अर्थात्, रिक्त प्रतीकों से भरा हुआ)। सभी शीर्ष टेप के सबसे बाईं ओर से प्रारंभ होते हैं। एक बार जब $M$ प्रारंभ हो जाता है, गणना पारगमन फलन द्वारा वर्णित नियमों के अनुसार आगे बढ़ती है। गणना तब तक जारी रहती है जब तक कि यह स्वीकृति स्थिति में प्रवेश नहीं कर जाती, जिस बिंदु पर यह रुक जाती है।

टू-स्टैक ट्यूरिंग मशीन

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

यह भी देखें

संदर्भ

↑ Sipser, Michael (2005). संगणना के सिद्धांत का परिचय. Thomson Course Technology. p. 148. ISBN 0-534-95097-3.
↑ Papadimitriou, Christos (1994). अभिकलनात्मक जटिलता. Addison-Wesley. p. 53. ISBN 0-201-53082-1.
↑ Martin, John (2010). भाषाओं का परिचय और संगणना का सिद्धांत. McGraw Hill. pp. 243–246. ISBN 978-0071289429.

[1] Sipser, Michael (2005). संगणना के सिद्धांत का परिचय. Thomson Course Technology. p. 148. ISBN 0-534-95097-3.

[2] Papadimitriou, Christos (1994). अभिकलनात्मक जटिलता. Addison-Wesley. p. 53. ISBN 0-201-53082-1.

[3] Martin, John (2010). भाषाओं का परिचय और संगणना का सिद्धांत. McGraw Hill. pp. 243–246. ISBN 978-0071289429.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
 {{turing}}
-मल्टी-टेप [[ट्यूरिंग मशीन]] ट्यूरिंग मशीन का एक प्रकार है जो कई टेपों का उपयोग करती है। पढ़ने और लिखने के लिए प्रत्येक टेप का अपना सिर होता है। प्रारंभ में, इनपुट टेप 1 पर दिखाई देता है, और अन्य खाली शुरू होते हैं।<ref>{{cite book |title=संगणना के सिद्धांत का परिचय|last1=Sipser |first1=Michael |year=2005|page=148|publisher=Thomson Course Technology|isbn=0-534-95097-3}}</ref>
+'''मल्टी-टेप ट्यूरिंग मशीन''' [[ट्यूरिंग मशीन]] का एक प्रकार है जो कई टेपों का उपयोग करती है। पढ़ने और लिखने के लिए प्रत्येक टेप का अपना सिर होता है। प्रारंभ में, निविष्ट टेप 1 पर दिखाई देता है, और अन्य खाली शुरू होते हैं।<ref>{{cite book |title=संगणना के सिद्धांत का परिचय|last1=Sipser |first1=Michael |year=2005|page=148|publisher=Thomson Course Technology|isbn=0-534-95097-3}}</ref>
-यह मॉडल सहज रूप से एकल-टेप मॉडल की तुलना में बहुत अधिक शक्तिशाली लगता है, लेकिन किसी भी मल्टी-टेप मशीन - चाहे कितने भी टेप हों - को एकल-टेप मशीन द्वारा केवल [[द्विघात फंक्शन]] का अधिक गणना समय का उपयोग करके अनुकरण किया जा सकता है।<ref>{{cite book |title=अभिकलनात्मक जटिलता|url=https://archive.org/details/computationalcom00papa |url-access=limited |last1=Papadimitriou |first1=Christos |year=1994|page=[https://archive.org/details/computationalcom00papa/page/n64 53]|publisher=Addison-Wesley|isbn=0-201-53082-1}}</ref> इस प्रकार, मल्टी-टेप मशीनें एकल-टेप मशीनों की तुलना में किसी भी अधिक फ़ंक्शन की गणना नहीं कर सकती हैं,<ref>{{cite book |title=भाषाओं का परिचय और संगणना का सिद्धांत|last1=Martin |first1=John |year=2010 |pages=243–246 |publisher=McGraw Hill |isbn= 978-0071289429}}</ref> और कोई भी मजबूत [[कम्प्यूटेशनल जटिलता सिद्धांत]] वर्ग (जैसे कि [[पी (जटिलता)]]) एकल-टेप और मल्टी-टेप मशीनों के बीच परिवर्तन से प्रभावित नहीं होता है।
+यह मॉडल सहज रूप से एकल-टेप मॉडल की तुलना में बहुत अधिक शक्तिशाली लगता है, लेकिन किसी भी मल्टी-टेप मशीन - चाहे कितने भी टेप हों - एकल-टेप मशीन द्वारा केवल [[Index.php?title=द्विघात फलन|द्विघात फलन]] का अधिक गणना समय का उपयोग करके अनुकरण किया जा सकता है।<ref>{{cite book |title=अभिकलनात्मक जटिलता|url=https://archive.org/details/computationalcom00papa |url-access=limited |last1=Papadimitriou |first1=Christos |year=1994|page=[https://archive.org/details/computationalcom00papa/page/n64 53]|publisher=Addison-Wesley|isbn=0-201-53082-1}}</ref> इस प्रकार, मल्टी-टेप मशीनें एकल-टेप मशीनों की तुलना में किसी भी अधिक फलन की गणना नहीं कर सकती हैं,<ref>{{cite book |title=भाषाओं का परिचय और संगणना का सिद्धांत|last1=Martin |first1=John |year=2010 |pages=243–246 |publisher=McGraw Hill |isbn= 978-0071289429}}</ref> और कोई भी मजबूत जटिलता वर्ग (जैसे बहुपद समय) एकल-टेप और मल्टी-टेप मशीनों के बीच परिवर्तन से प्रभावित नहीं होता है
 == औपचारिक परिभाषा ==
-<math>k </math>-टेप ट्यूरिंग मशीन को औपचारिक रूप से 7-[[ टपल ]] के रूप में परिभाषित किया जा सकता है <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>ट्यूरिंग मशीन के नोटेशन का अनुसरण करते हुए:
+<math>k </math>-टेप ट्यूरिंग मशीन को औपचारिक रूप से 7-[[ टपल ]] के रूप में परिभाषित किया जा सकता है <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math>ट्यूरिंग मशीन के संकतन का अनुसरण करते हुए:
 * <math>\Gamma</math> टेप वर्णमाला प्रतीकों का एक सीमित, गैर-रिक्त सेट है;
 * <math>b \in \Gamma</math> रिक्त प्रतीक है (गणना के दौरान किसी भी चरण में टेप पर अनंत बार आने वाला एकमात्र प्रतीक);
-* <math>\Sigma\subseteq\Gamma\setminus\{b\}</math> इनपुट प्रतीकों का सेट है, यानी, प्रारंभिक टेप सामग्री में प्रदर्शित होने की अनुमति वाले प्रतीकों का सेट;
+* <math>\Sigma\subseteq\Gamma\setminus\{b\}</math> निविष्ट प्रतीकों का सेट है, यानी, प्रारंभिक टेप सामग्री में प्रदर्शित होने की अनुमति वाले प्रतीकों का सेट;
-* <math>Q</math> राज्यों का एक सीमित, गैर-रिक्त सेट है;
+* <math>Q</math> अवस्थायों का एक सीमित, गैर-रिक्त सेट है;
 * <math>q_0 \in Q</math> प्रारंभिक अवस्था है;
 * <math>F \subseteq Q</math> अंतिम अवस्थाओं या स्वीकार करने वाली अवस्थाओं का समूह है। कहा जाता है कि प्रारंभिक टेप सामग्री को स्वीकार कर लिया गया है <math>M</math> यदि यह अंततः एक स्थिति में रुक जाता है <math>F</math>.
-* <math>\delta: (Q \setminus F) \times \Gamma^k \to Q \times \Gamma^k \times \{L,R\}^k</math> एक [[आंशिक कार्य]] है जिसे [[राज्य संक्रमण प्रणाली]] कहा जाता है, जहां L बाईं शिफ्ट है, R दाईं शिफ्ट है।
+* <math>\delta: (Q \setminus F) \times \Gamma^k \to Q \times \Gamma^k \times \{L,R\}^k</math> एक आंशिक फलन है जिसे पारगमन फलन कहा जाता है, जहां L बाईं शिफ्ट है, R दाईं शिफ्ट है।
-ए <math>k</math>-टेप ट्यूरिंग मशीन <math>M</math> निम्नानुसार गणना करता है। शुरू में, <math>M</math> उसका इनपुट प्राप्त करता है <math>w=w_1w_2...w_n \in \Sigma^* </math> सबसे बाईं ओर <math>n</math> पहले टेप की स्थिति, पहले टेप के साथ-साथ अन्य टेपों का शेष भाग रिक्त है (अर्थात्, रिक्त प्रतीकों से भरा हुआ)। सभी शीर्ष टेप के सबसे बाईं ओर से प्रारंभ होते हैं। एक बार <math>M</math> प्रारंभ हो गया है, गणना संक्रमण फ़ंक्शन द्वारा वर्णित नियमों के अनुसार आगे बढ़ती है। गणना तब तक जारी रहती है जब तक कि यह स्वीकृति स्थिति में प्रवेश नहीं कर जाती, जिस बिंदु पर यह रुक जाती है।
+<math>k</math>-टेप ट्यूरिंग मशीन <math>M</math> निम्नानुसार गणना करता है। शुरू में, <math>M</math> उसका निविष्ट प्राप्त करता है <math>w=w_1w_2...w_n \in \Sigma^* </math> सबसे बाईं ओर <math>n</math> पहले टेप की स्थिति, पहले टेप के साथ-साथ अन्य टेपों का शेष भाग रिक्त है (अर्थात्, रिक्त प्रतीकों से भरा हुआ)। सभी शीर्ष टेप के सबसे बाईं ओर से प्रारंभ होते हैं। एक बार जब <math>M</math> प्रारंभ हो जाता है, गणना पारगमन फलन द्वारा वर्णित नियमों के अनुसार आगे बढ़ती है। गणना तब तक जारी रहती है जब तक कि यह स्वीकृति स्थिति में प्रवेश नहीं कर जाती, जिस बिंदु पर यह रुक जाती है।
-== दो-स्टैक ट्यूरिंग मशीन ==
+== टू-स्टैक ट्यूरिंग मशीन ==
-दो-स्टैक ट्यूरिंग मशीनों में एक रीड-ओनली इनपुट और दो स्टोरेज टेप होते हैं। यदि किसी टेप पर कोई सिर बाईं ओर जाता है तो उस टेप पर एक रिक्त स्थान मुद्रित होता है, लेकिन लाइब्रेरी से एक प्रतीक मुद्रित किया जा सकता है।
+टू-स्टैक ट्यूरिंग मशीनों में एक केवल पठनीय निविष्ट और दो भंड़ारण टेप होते हैं। यदि किसी टेप पर कोई सिर बाईं ओर जाता है तो उस टेप पर एक रिक्त स्थान मुद्रित होता है, लेकिन लाइब्रेरी से एक प्रतीक मुद्रित किया जा सकता है।
 == यह भी देखें ==

Anonymous

Search

मल्टीटेप ट्यूरिंग मशीन: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:44, 6 July 2023

Contents

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

टू-स्टैक ट्यूरिंग मशीन

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

मल्टीटेप ट्यूरिंग मशीन: Difference between revisions

Revision as of 18:44, 6 July 2023

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

टू-स्टैक ट्यूरिंग मशीन

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories