यह दिखाने के लिए कि एक भाषा निर्णायक है, हमें एक ट्यूरिंग मशीन बनाने के लिए की आवश्यकता है जो भाषा के वर्णमाला से किसी भी इनपुट स्ट्रिंग पर रुकेगी। चूंकि M एक dfa है, हमारे पास पहले से ही ट्यूरिंग मशीन है और केवल यह दिखाने की आवश्यकता है कि dfa प्रत्येक इनपुट पर रुकता है।
आप निर्णायकता की गणना कैसे करते हैं?
एक भाषा निर्णायक होती है यदि और केवल तभी जब वह और उसके पूरक पहचानने योग्य हों। सबूत। यदि कोई भाषा पर्णपाती है, तो उसका पूरक निर्णायक है (पूरक के तहत बंद करके)।
आप ट्यूरिंग डिसिडेबिलिटी कैसे साबित करते हैं?
साबित करें कि जिस भाषा को वह पहचानता है वह दी गई भाषा के बराबर है और एल्गोरिथम सभी इनपुट पर रुक जाता है। यह साबित करने के लिए कि दी गई भाषा ट्यूरिंग-पहचानने योग्य है: एक एल्गोरिथम का निर्माण करें जो वास्तव में उन स्ट्रिंग्स को स्वीकार करता है जो भाषा में हैंइसे या तो अस्वीकार करना चाहिए या किसी भी स्ट्रिंग पर लूप करना चाहिए जो भाषा में नहीं है।
आपको कैसे पता चलेगा कि कोई भाषा पहचानने योग्य है?
एक भाषा L को पहचाना जा सकता है यदि और केवल अगर L के लिए एक सत्यापनकर्ता मौजूद है, जहां एक सत्यापनकर्ता एक ट्यूरिंग मशीन है जो सभी इनपुट पर और सभी के लिए रुकती है।, वुलि. वी w, c⟩ स्वीकार करता है।
आप कैसे दिखाते हैं कि कोई समस्या अनिर्णीत है?
समग्र समस्या अनिर्णीत है
रोकने की समस्या का उपयोग यह दिखाने के लिए किया जा सकता है कि अन्य समस्याएं अनिर्णीत हैं। समग्रता समस्या: एक फ़ंक्शन (या प्रोग्राम) F को कुल कहा जाता है यदि F(x) को सभी x के लिए परिभाषित किया जाता है (या इसी तरह, यदि F(x) सभी x के लिए रुकता है)। यह निर्धारित करना कि कोई फ़ंक्शन F कुल है या नहीं, अनिर्णीत है।
