मल्टी ट्रैक ट्यूरिंग मशीन
मल्टी-ट्रैक ट्यूरिंग मशीन, एक विशिष्ट प्रकार की मल्टी-टेप ट्यूरिंग मशीन, जिसमें कई ट्रैक होते हैं, लेकिन सिर्फ एक टेप हेड सभी पटरियों को पढ़ता और लिखता है। यहाँ, एक एकल टेप हेड से n प्रतीकों को पढ़ा जाता हैnएक कदम पर पटरियों। यह एक सामान्य सिंगल-ट्रैक सिंगल-टेप ट्यूरिंग मशीन की तरह पुनरावर्ती भाषाओं को स्वीकार करता है।
एक मल्टी-ट्रैक ट्यूरिंग मशीन को औपचारिक रूप से 6-ट्यूपल (क्यू, एक्स, ∑,,, q 0 , F) के रूप में वर्णित किया जा सकता है , जहां -
Q राज्यों का एक समुच्चय है
X टेप वर्णमाला है
∑ इनपुट वर्णमाला है
δ जहां राज्यों और प्रतीकों पर एक संबंध है
δ (क्यू मैं , [एक 1 , एक 2 , एक 3 , ....]) = (क्यू j , [ख 1 , बी 2 , बी 3 , ....], Left_shift या Right_shift)
q0 प्रारंभिक अवस्था है
F अंतिम राज्यों का सेट है
Note - हर एक-ट्रैक ट्यूरिंग मशीन के लिए S, एक बराबर मल्टी-ट्रैक ट्यूरिंग मशीन है M ऐसा है कि L(S) = L(M)।