मल्टीटेप ट्यूरिंग मशीन

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

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

$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$ प्रारंभ हो गया है, गणना संक्रमण फ़ंक्शन द्वारा वर्णित नियमों के अनुसार आगे बढ़ती है। गणना तब तक जारी रहती है जब तक कि यह स्वीकृति स्थिति में प्रवेश नहीं कर जाती, जिस बिंदु पर यह रुक जाती है।

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

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

यह भी देखें

• ट्यूरिंग मशीन
• यूनिवर्सल ट्यूरिंग मशीन
• वैकल्पिक ट्यूरिंग मशीन
• संभाव्य ट्यूरिंग मशीन
• ट्यूरिंग मशीन समकक्ष