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

Latest revision as of 11:41, 14 August 2023

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

एक मानक 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

@@ Line 3: / Line 3: @@
 '''मल्टीट्रैक ट्यूरिंग मशीन''' एक विशिष्ट प्रकार की [[मल्टी-टेप ट्यूरिंग मशीन]] है।
-एक मानक एन-टेप ट्यूरिंग मशीन में, एन हेड्स एन ट्रैक्स के साथ स्वतंत्र रूप से चलते हैं। एन-ट्रैक ट्यूरिंग मशीन में, एक हेड सभी ट्रैकों को एक साथ पढ़ता और लिखता है। एन-ट्रैक ट्यूरिंग मशीन में एक टेप स्थिति में टेप वर्णमाला से एन प्रतीक होते हैं। यह मानक ट्यूरिंग मशीन के समतुल्य है और इसलिए [[Index.php?title=पुनरावर्ती रूप से गणना योग्य भाषाओं|पुनरावर्ती रूप से गणना योग्य भाषाओं]] को सटीक रूप से स्वीकार करता है।
+एक मानक 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>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>\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> एक [[आंशिक कार्य]] है जिसे संक्रमण फलन कहा जाता है।
+* <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 \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>.
+संक्रमण फलन को प्रतिस्थापित करके एक गैर-नियतात्मक संस्करण को परिभाषित किया जा सकता है <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>.
 == मानक ट्यूरिंग मशीन के समतुल्यता का प्रमाण ==
-इससे साबित होगा कि दो-ट्रैक ट्यूरिंग मशीन एक मानक ट्यूरिंग मशीन के बराबर है। इसे एन-ट्रैक ट्यूरिंग मशीन के लिए सामान्यीकृत किया जा सकता है। मान लीजिए कि L एक पुनरावर्ती गणना योग्य भाषा है। चलो एम = <math>\langle Q, \Sigma, \Gamma, \delta, q_0, F \rangle </math> मानक ट्यूरिंग मशीन हो जो एल को स्वीकार करती हो। लेट एम' एक दो-ट्रैक ट्यूरिंग मशीन है। M=M' को सिद्ध करने के लिए यह दिखाया जाना चाहिए कि M <math> \subseteq </math> एम' और एम' <math> \subseteq </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' के इनपुट प्रतीक 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>
-एम= <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:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:ट्यूरिंग मशीन]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 11:41, 14 August 2023

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

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 11:41, 14 August 2023

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

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories