मल्टी-टेप ट्यूरिंग मशीन
मल्टी-टेप ट्यूरिंग मशीनों में कई टेप होते हैं जहां प्रत्येक टेप को एक अलग सिर के साथ एक्सेस किया जाता है। प्रत्येक सिर दूसरे सिर से स्वतंत्र रूप से आगे बढ़ सकता है। प्रारंभ में इनपुट 1 टेप पर है और अन्य रिक्त हैं। पहले पर, पहले टेप को इनपुट द्वारा कब्जा कर लिया जाता है और दूसरे टेप को खाली रखा जाता है। अगला, मशीन अपने सिर के नीचे लगातार प्रतीकों को पढ़ती है और टीएम प्रत्येक टेप पर एक प्रतीक प्रिंट करता है और अपने सिर को स्थानांतरित करता है।
एक मल्टी-टेप ट्यूरिंग मशीन को औपचारिक रूप से 6-ट्यूपल (Q, X, B,,, q 0 , F) के रूप में वर्णित किया जा सकता है -
Q राज्यों का एक समुच्चय है
X टेप वर्णमाला है
B रिक्त प्रतीक है
δ जहां राज्यों और प्रतीकों पर एक संबंध है
X: Q × X k → Q × (X × {Left_shift, Right_shift, No_shift}) k
जहाँ ये है k टेपों की संख्या
q0 प्रारंभिक अवस्था है
F अंतिम राज्यों का सेट है
Note - हर मल्टी-टेप ट्यूरिंग मशीन में एक सिंगल-टेप ट्यूरिंग मशीन होती है।