अर्ध-अनंत टेप ट्यूरिंग मशीन
अर्ध-अनंत टेप वाली एक ट्यूरिंग मशीन का बायां छोर होता है, लेकिन दायां छोर नहीं होता है। बाएं छोर एक अंत मार्कर के साथ सीमित है।
यह एक दो ट्रैक वाला टेप है -
Upper track - यह प्रारंभिक सिर की स्थिति के दाईं ओर कोशिकाओं का प्रतिनिधित्व करता है।
Lower track - यह कोशिकाओं को रिवर्स ऑर्डर में प्रारंभिक सिर की स्थिति के बाईं ओर प्रस्तुत करता है।
अनंत लंबाई इनपुट स्ट्रिंग शुरू में सन्निहित टेप कोशिकाओं में टेप पर लिखा जाता है।
मशीन प्रारंभिक अवस्था से शुरू होती है q0और सिर बाईं ओर के सिरे 'एंड ’से स्कैन होता है। प्रत्येक चरण में, यह अपने सिर के नीचे टेप पर प्रतीक को पढ़ता है। यह उस टेप सेल पर एक नया प्रतीक लिखता है और फिर यह सिर को बाएँ या दाएँ एक टेप सेल में ले जाता है। एक संक्रमण फ़ंक्शन निर्धारित किए जाने वाले कार्यों को निर्धारित करता है।
इसके दो विशेष राज्य कहे जाते हैं accept state तथा reject state। यदि किसी भी समय यह स्वीकृत स्थिति में प्रवेश करता है, तो इनपुट स्वीकार किया जाता है और यदि यह अस्वीकार स्थिति में प्रवेश करता है, तो इनपुट टीएम द्वारा खारिज कर दिया जाता है। कुछ मामलों में, यह कुछ निश्चित इनपुट प्रतीकों के लिए स्वीकार या अस्वीकार किए बिना असीम रूप से चलता रहता है।
Note - अर्ध-अनंत टेप वाली ट्यूरिंग मशीनें मानक ट्यूरिंग मशीनों के बराबर हैं।