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

{{turing}}

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

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

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

जहाँ

* <math>Q</math> राज्यों का एक सीमित समूह है;
* <math>\Sigma \subseteq \Gamma \setminus\{b\} </math> इनपुट प्रतीकों का एक सीमित सेट है, अर्थात्, प्रारंभिक टेप सामग्री में प्रदर्शित होने की अनुमति वाले प्रतीकों का एक सेट है;
*<math>\Gamma</math> टेप वर्णमाला प्रतीकों का एक सीमित सेट है;
* <math>q_0 \in Q</math> प्रारंभिक अवस्था है;
* <math>F \subseteq Q</math> अंतिम या स्वीकार करने वाली अवस्थाओं का समुच्चय है;
* <math>\delta: \left(Q \backslash F \times \Gamma^n \right) \rightarrow \left( Q \times \Gamma^n \times \{L,R\} \right)</math> एक [[Index.php?title=आंशिक फलन|आंशिक फलन]] है जिसे संक्रमण फलन कहा जाता है।
: कभी-कभी इसे भी दर्शाया जाता है <math>\delta \left(Q_i,[x_1,x_2...x_n]\right)=(Q_j,[y_1,y_2...y_n],d)</math>, जहाँ <math>d \in \{L,R\}</math>.

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

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

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

M= <math>\langle Q, \Sigma \times {B}, \Gamma \times \Gamma, \delta ', q_0, F \rangle </math> संक्रमण फलन के साथ <math>\delta \left(q_i,[x_1,x_2]\right)=\delta ' \left(q_i,[x_1,x_2]\right)</math>

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

== संदर्भ ==
{{Reflist}}
*Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. {{isbn|0-321-32221-5}}. Chapter 8.6: Multitape Machines: pp 269–271
[[Category: ट्यूरिंग मशीन]] 



[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]