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

मल्टीट्रैक ट्यूरिंग मशीन एक विशिष्ट प्रकार की मल्टी-टेप ट्यूरिंग मशीन है।

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

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

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

जहाँ

• $Q$ राज्यों का एक सीमित समूह है;
• $\Sigma \subseteq \Gamma \setminus \{b\}$ इनपुट प्रतीकों का एक सीमित सेट है, यानी, प्रारंभिक टेप सामग्री में प्रदर्शित होने की अनुमति वाले प्रतीकों का एक सेट है;
• $\Gamma$ टेप वर्णमाला प्रतीकों का एक सीमित सेट है;
• $q_{0}\in Q$ प्रारंभिक अवस्था है;
• $F\subseteq Q$ अंतिम या स्वीकार करने वाली अवस्थाओं का समुच्चय है;
• $\delta :\left(Q\backslash F\times \Gamma ^{n}\right)\rightarrow \left(Q\times \Gamma ^{n}\times \{L,R\}\right)$ एक आंशिक फलन है जिसे संक्रमण फलन कहा जाता है।

कभी-कभी इसे भी दर्शाया जाता है $\delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)$, जहाँ $d\in \{L,R\}$.

संक्रमण फलन को प्रतिस्थापित करके एक गैर-नियतात्मक संस्करण को परिभाषित किया जा सकता है $\delta$ एक संक्रमण संबंध द्वारा $\delta \subseteq \left(Q\backslash F\times \Gamma ^{n}\right)\times \left(Q\times \Gamma ^{n}\times \{L,R\}\right)$.

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

इससे साबित होगा कि दो-ट्रैक ट्यूरिंग मशीन एक मानक ट्यूरिंग मशीन के बराबर है। इसे एन-ट्रैक ट्यूरिंग मशीन के लिए सामान्यीकृत किया जा सकता है। मान लीजिए कि L एक पुनरावर्ती गणना योग्य भाषा है। चलो एम = $\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle$ मानक ट्यूरिंग मशीन हो जो एल को स्वीकार करती हो। लेट एम' एक दो-ट्रैक ट्यूरिंग मशीन है। M=M' को सिद्ध करने के लिए यह दिखाया जाना चाहिए कि M $\subseteq$ एम' और एम' $\subseteq$ एम

• $M\subseteq M'$

यदि दूसरे ट्रैक को नजरअंदाज कर दिया जाए तो एम और एम' स्पष्ट रूप से समकक्ष हैं।

• $M'\subseteq M$

दो-ट्रैक ट्यूरिंग मशीन के समतुल्य एक-ट्रैक ट्यूरिंग मशीन के टेप वर्णमाला में एक ऑर्डर की गई जोड़ी होती है। ट्यूरिंग मशीन M' के इनपुट प्रतीक a को ट्यूरिंग मशीन M के ऑर्डर किए गए जोड़े [x,y] के रूप में पहचाना जा सकता है। वन-ट्रैक ट्यूरिंग मशीन है:

एम= $\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle$ संक्रमण फ़ंक्शन के साथ $\delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)$ यह मशीन एल भी स्वीकार करती है।

संदर्भ

• Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269–271