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

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

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

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

यह भी देखें

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