मेरी सरल ट्यूरिंग मशीन

Question

मैं सबसे सरल ट्यूरिंग मशीन को समझने और कार्यान्वित करने की कोशिश कर रहा हूं और अगर मुझे समझ में आ रहा है तो प्रतिक्रिया चाहिए।

हम एक अनंत टेप है और निर्देश सारणी (एक सरणी शुरू में 0 पर सूचक के साथ टी कहा जाता है का कहना है की सुविधा देता है):

(S , R , W , D , N) 

S->STEP (Start at step 1) 
R->READ (0 or 1) 
W->WRITE (0 or 1) 
D->DIRECTION (0=LEFT 1=RIGHT) 
N->NEXTSTEP (Non existing step is HALT) 

मेरे समझ है कि एक 3-राज्य 2-प्रतीक सरल मशीन है । 3-राज्य मुझे समझ में नहीं आता है। 2-प्रतीक क्योंकि हम पढ़ने/लिखने के लिए 0 और 1 का उपयोग करते हैं।

उदाहरण के लिए:

(1,0,1,1,2) 
(1,1,0,1,2) 

चरण 1 से शुरू करता है, तो पढ़ें 0 है तो {लिखें 1, सही) और ले जाएँ {लिखें 0, दाईं ओर ले जाएं) और फिर कदम पर जाने के 2 - जो मौजूद नहीं है जो प्रोग्राम रोकता है।

3-राज्य का क्या अर्थ है? क्या यह मशीन ट्यूरिंग मशीन के रूप में गुजरती है? क्या हम और अधिक सरल बना सकते हैं?

Answer 1

मेरा मानना ​​है कि राज्य की अवधारणा मूल रूप से Finite State Machines जैसी ही है। अगर मुझे याद है, तो आपको एक अलग समाप्ति स्थिति की आवश्यकता है, जिस पर ट्यूरिंग मशीन प्रोग्राम चलाने के बाद संक्रमण कर सकती है। क्यों 3 राज्यों में मुझे लगता है कि अन्य दो राज्य क्रमशः इंटिलाइज़ेशन और निष्पादन के लिए हैं।

दुर्भाग्य से इनमें से कोई भी सही होने की गारंटी नहीं है, लेकिन मैंने सोचा कि मैं अपने विचार पोस्ट करूंगा क्योंकि सवाल 5 घंटे के लिए अनुत्तरित नहीं था। मुझे संदेह है कि क्या आप इस सवाल को cstheory.stackexchange.com पर फिर से पूछना चाहते हैं, तो आपको एक बेहतर/अधिक निश्चित उत्तर मिल सकता है।

Answer 2

ट्यूरिंग मशीनों के संदर्भ में "राज्य" को स्पष्ट किया जाना चाहिए: (i) वर्तमान निर्देश, या (ii) वर्तमान निर्देश के साथ टेप पर प्रतीकों की सूची, या (iii) स्कैन किए गए प्रतीक के बाईं ओर या स्कैन किए गए प्रतीक के दाईं ओर स्थित वर्तमान निर्देश के साथ टेप पर प्रतीकों की सूची। Reference

Answer 3

मुझे लगता है कि भ्रम "राज्यों" के बजाय "चरणों" के उपयोग से हो सकता है। आप मशीन की स्थिति के बारे में सोच सकते हैं क्योंकि इसकी याद में इसकी कीमत है (हालांकि पिछले पोस्टर के रूप में, कुछ लोग टेप की सामग्री को शामिल करने के लिए मशीन की स्थिति भी लेते हैं - हालांकि, मुझे नहीं लगता कि परिभाषा प्रासंगिक है आपके प्रश्न के लिए)। यह संभव है कि शब्दावली में यह परिवर्तन आपके भ्रम के केंद्र में हो सकता है। मुझे समझाने दो कि मुझे क्या लगता है कि आप सोच रहे हैं। :)

आपने पांच संख्याओं की सूचियां दी - उदाहरण के लिए, (1,0,1,1,2)। जैसा कि आप सही ढंग से बताते हैं, इसका अर्थ व्याख्या (बाएं से दाएं पढ़ने) के रूप में किया जाना चाहिए "यदि मशीन राज्य 1 में है और वर्तमान वर्ग में 0 है, तो 1 प्रिंट करें, दाएं स्थानांतरित करें, और राज्य में बदलें 2." हालांकि, "चरण" शब्द का उपयोग यह सुझाव देता है कि "चरण 2" का पालन "चरण 3" आदि के बाद किया जाना चाहिए, जब वास्तव में एक ट्यूरिंग मशीन राज्यों के बीच आगे जा सकती है (और निश्चित रूप से, वहां केवल कई संभावित राज्य हो सकते हैं)।

तो आपके सवालों के जवाब:

• ट्यूरिंग मशीन रखने का ट्रैक "कहा गया है" नहीं "चरण";
• जो आपने वर्णन किया है वह वैध ट्यूरिंग मशीन है;
• एक सरल (हालांकि अन्यथा अनिच्छुक) ट्यूरिंग मशीन एचएएलटी राज्य में शुरू होगी।

संपादन: व्याकरण, स्वरूपण, और ट्यूरिंग मशीनों के एक अनावश्यक विवरण को हटा दिया गया।

रिस्पांस टिप्पणी करने के लिए: मुझे सही अगर मैं अपनी टिप्पणी की गलत व्याख्या कर रहा हूँ, लेकिन मैं एक ट्यूरिंग मशीन सुझाव देने के लिए एक समय में एक से अधिक राज्य में हो सकता है, यह मतलब नहीं था कि केवल संभावित स्थितियों की संख्या कर सकते हैं कोई सीमित संख्या हो। उदाहरण के लिए, 3-स्टेट मशीन के लिए, आप संभावित राज्य ए, बी, और सी लेबल कर सकते हैं (उदाहरण के लिए आपने दो संभावित राज्यों को '1' और '2' के रूप में लेबल किया है) किसी भी समय, उन मूल्यों में से एक (राज्य) मशीन की स्मृति में होगा। हम कहेंगे, "मशीन राज्य ए में है" या "मशीन राज्य बी में है, आदि। (आपकी मशीन राज्य '1' में शुरू होती है और इसे '2' में प्रवेश करने के बाद समाप्त हो जाती है)।

इसके अलावा, यह अब मुझे स्पष्ट नहीं है कि आप "सरल/एस्ट" मशीन से क्या मतलब रखते हैं। सबसे छोटी ज्ञात यूनिवर्सल ट्यूरिंग मशीन (यानी, एक ट्यूरिंग मशीन जो उचित टेप के बाद एक और ट्यूरिंग मशीन अनुकरण कर सकती है) को 2 राज्यों और 5 प्रतीकों की आवश्यकता होती है (the relevant Wikipedia article देखें)।

दूसरी तरफ, यदि आप एक ही गणना शक्ति के साथ ट्यूरिंग मशीन से कुछ आसान खोज रहे हैं, तो Post-Turing machines रुचि का हो सकता है।