यह कैसे बताना है कि मशीन ट्यूरिंग मशीन समतुल्य है

Question

मुझे a list of Turing machine equivalents का विकिपीडिया आलेख मिला। हालांकि, यह निर्धारित करने के तरीके को नहीं बताता है कि दी गई मशीन ट्यूरिंग मशीन समकक्ष है या नहीं।

क्या मुझे इसे साबित करने के लिए ट्यूरिंग मशीन की परिभाषा का उपयोग करने की आवश्यकता है? क्या आप एक उदाहरण दे सकते हैं?

धन्यवाद।

Answer 1

कुछ ट्यूरिंग पूर्ण करने का मानक तरीका आपकी मशीन में टीएम समकक्षों में से एक को लागू करना है। यदि ऐसा करना संभव है, तो आपकी मशीन ट्यूरिंग-पूर्ण है। यदि यह नहीं है, तो यह नहीं है। तो अगर मैं साबित करने की कोशिश कर रहा था, तो कहें कि एक नई प्रोग्रामिंग भाषा पूरी तरह से ट्यूरिंग कर रही है, मैं टीएम समकक्ष को चुनना चाहता हूं जो कार्यान्वित करने के लिए सबसे आसान है, और फिर दिखाएं कि मेरी प्रोग्रामिंग भाषा इसे अनुकरण कर सकती है।

Answer 2

मेरे सिर के शीर्ष में: यदि आपकी मशीन ज्ञात ट्यूरिंग मशीन समकक्ष मशीनों में से एक को अनुकरण कर सकती है, तो आपकी मशीन भी ट्यूरिंग मशीन समकक्ष है।

शायद इस तरह कुछ करने के बारे में जाने का सबसे आसान तरीका।

संपादित करें: मैं यह नहीं कह रहा हूं कि मशीन के लिए ट्यूरिंग मशीन समकक्ष होने की आवश्यकता है, यह सब कुछ हो सकता है। शायद कोई भी जो सैद्धांतिक सूचना विज्ञान में थोड़ा अधिक कुशल है, इस पर मुझे साफ़ कर सकता है?

Answer 3

वास्तव में यह वास्तव में सिद्ध नहीं किया जा सकता है। कम से कम, इन सामान्य समानता प्रमाणों को पूरी तरह औपचारिक रूप से औपचारिक रूप से सैद्धांतिक कंप्यूटर विज्ञान में अपेक्षा की अपेक्षा अधिक औपचारिक तर्क की आवश्यकता हो सकती है। (यदि आप असहमत हैं, तो मुझे बताओ! मैं इसके बारे में चर्चा करने के लिए उत्सुक हूं।)

हालांकि, यह संदर्भ से ज्यादातर स्पष्ट है। आप गणना के एक अन्य मॉडल के भीतर गणना ए की योजना के "मशीन" का सिमुलेशन बनाने का प्रयास करते हैं। इसका मतलब है कि बी ए अनुकरण कर सकता है, और इसलिए ए की पूरी शक्ति है। यदि आप इसके विपरीत करते हैं, तो इन दो मॉडल को बुलाया जाता है बराबर।