रोकथाम की समस्या पूरी भाषाओं को ट्यूर करने के लिए हल नहीं की जा सकती है और इसे कुछ गैर-टीसी भाषाओं जैसे कि यह हमेशा रोकता है, के लिए इसे हल किया जा सकता है।गैर-ट्यूरिंग-पूर्ण भाषाओं में हेलिंग
मैं सोच रहा था कि ऐसी कोई भाषाएं हैं जिनमें रुकने की क्षमता और रोक नहीं है, लेकिन एक एल्गोरिदम स्वीकार करता है जो यह निर्धारित कर सकता है कि यह रोकता है या नहीं।
हां। इस प्रकार का एक महत्वपूर्ण वर्ग primitive recursive functions है। इस वर्ग में उन सभी मूलभूत चीजें शामिल हैं जिन्हें आप संख्याओं (अतिरिक्त, गुणा, इत्यादि) के साथ करने में सक्षम होने की उम्मीद करते हैं, साथ ही साथ कुछ जटिल वर्ग जैसे @adrian ने उल्लेख किया है (नियमित अभिव्यक्ति/सीमित ऑटोमाटा, संदर्भ मुक्त व्याकरण/पुशडाउन ऑटोमेटा)। हालांकि, ऐसे कार्य मौजूद हैं जो आदिम रिकर्सिव नहीं हैं, जैसे कि Ackermann function।
आदिम पुनरावर्ती कार्यों को समझना वास्तव में बहुत आसान है। वे वे कार्य हैं जिन्हें आप प्रोग्रामिंग भाषा में प्राप्त कर सकते हैं, जिसमें कोई वास्तविक रिकर्सन नहीं था (इसलिए कोई फ़ंक्शन एफ स्वयं को कॉल नहीं कर सकता है, चाहे सीधे या किसी अन्य फ़ंक्शन जी को कॉल करके, जिसे फिर f कहते हैं, आदि) और इसमें कोई समय-समय नहीं है, इसके बजाय लूप के लिए बाध्य किया। एक बाध्य फॉर-लूप एक जैसा है "मैं 1 से आर तक" जहां आर एक चर है जिसे प्रोग्राम में पहले से ही गणना की जा चुकी है; भी, मैं फॉर-लूप के भीतर संशोधित नहीं किया जा सकता है। ऐसी प्रोग्रामिंग भाषा का बिंदु यह है कि प्रत्येक प्रोग्राम रोकता है।
हमारे द्वारा लिखे जाने वाले अधिकांश कार्यक्रम वास्तव में आदिम रिकर्सिव हैं (मेरा मतलब है, ऐसी भाषा में अनुवाद किया जा सकता है)।
रुको, ऐसे प्रकार के नियमित अभिव्यक्तियां हैं जो * हमेशा रोकती हैं * (जैसा कि ओपी कहता है), या जिस तरह से रुक सकता है, लेकिन कोई हमेशा यह कह सकता है कि यह करता है या नहीं? इस प्रश्न के कारण पूछना: http://stackoverflow.com/questions/1241215/do-all-regular-expressions-halt – hsribei
मुझे नहीं पता कि मैं कहूंगा कि नियमित अभिव्यक्ति वास्तव में गणना के मॉडल को परिभाषित करती है। किसी भी मामले में, सीमित समय में बताना हमेशा संभव होता है कि दी गई स्ट्रिंग एक नियमित नियमित अभिव्यक्ति से मेल खाती है या नहीं। –
halting problem भाषाओं पर कार्य नहीं करता है। इसके बजाय, यह मशीनों (यानी, प्रोग्राम) पर कार्य करता है: यह पूछता है कि दिया गया प्रोग्राम किसी दिए गए इनपुट पर रोकता है या नहीं।
शायद आप पूछने के लिए यह गणना के अन्य मॉडलों के लिए हल किया जा सकता है कि क्या मतलब है (नियमित अभिव्यक्ति है, जो आप का उल्लेख की तरह, लेकिन यह भी push-down automata की तरह)।
लंगड़ा, सामान्य रूप में, परिमित संसाधनों (जैसे नियमित अभिव्यक्ति या, समतुल्य रूप, परिमित ऑटोमेटा, जो कोई बाह्य भंडारण राज्यों की एक निश्चित संख्या और राशि) के साथ मॉडल में पता लगाया जा सकता है। यह आसानी से द्वारा सभी संभावित कॉन्फ़िगरेशन का आकलन करके जांच कर रहा है और यह जांच कर रहा है कि मशीन एक ही कॉन्फ़िगरेशन में दो बार प्रवेश करती है (अनंत लूप का संकेत देती है); सीमित संसाधनों के साथ, हम को दोहराए गए कॉन्फ़िगरेशन को देखते हुए मशीन को रोक नहीं सकते हैं, इससे पहले हम समय की ऊपरी सीमा पर रख सकते हैं।
आमतौर पर, अनंत संसाधनों (असीम TM और पीडीए, उदाहरण के लिए) के साथ मॉडल, रोकने जाँच नहीं किया जा सकता है, लेकिन यह अलग-अलग मॉडल और उनके खुले समस्याओं की जांच के लिए सबसे अच्छा होगा।
(सभी विकिपीडिया लिंक के लिए क्षमा करें, लेकिन यह वास्तव में सवाल इस तरह के लिए एक बहुत अच्छा स्रोत है।)
क्या सभी मशीनों को उन इनपुट के सेट के रूप में प्रदर्शित नहीं किया जा सकता है, जिन्हें वे स्वीकार करते हैं, यानी एक भाषा? – FryGuy
@FryGuy: लेकिन आप इस जानकारी को किसी प्रोग्राम को नहीं दे सकते, क्योंकि वह प्रतिनिधित्व अनंत है। –
@ एरेक्स लेकिन आप एक भाषा के रूप में रोकथाम की समस्या का प्रतिनिधित्व कर सकते हैं, भाषा जो सभी कार्यक्रमों को रोकती है। – Spudd86
कम जवाब है हां, और इस तरह भाषाओं भी अत्यंत उपयोगी हो सकता है।
इसके बारे में एक चर्चा LTU पर कुछ महीने पहले हुई थी: http://lambda-the-ultimate.org/node/2846
आपको "ट्यूरिंग पूर्ण" कहने के लिए शीर्षक संपादित करना चाहिए; हालांकि पहले यह एक क्रैकपॉट प्रश्न था (उदा।"गैर-ट्यूरिंग" = "ट्यूरिंग मशीनों जैसी चीजों की हमारी मूर्ख परिभाषाओं से सीमित नहीं है।") – Domenic