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

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

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

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

एक मल्टीट्रैक ट्यूरिंग मशीन के साथ $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)$.

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

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

• $M\subseteq M'$

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

• $M'\subseteq M$

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

M= $\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)$

यह मशीन L भी स्वीकार करती है।

संदर्भ

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