कहें कि ट्यूरिंग मशीनें एम 1, एम 2, एम 3, वे भाषाएं हैं जिन्हें वे क्रमशः एल (एम 1), एल (एम 2), और एल (एम 3) मानते हैं। निम्नलिखित भाषा एल = {(एम 1, एम 2, एम 3): एल (एम 1), एल (एम 2), और एल (एम 3) बराबर नहीं हैं} क्या भाषा क्षीण है? आवर्ती रूप से गणना योग्य? या न तो?डिकिडेबिलिटी और रिकर्सिव एन्युमेरिबिलिटी
Let एम एम मैं, मैं एक मशीन इनपुट I पर कुछ अन्य मशीन एम मैं चल रहा है और true लौटाता है यदि M मैं अंततः I पर रुकती है, और हमेशा के लिए अन्यथा लूप simulates कि हो।
चलो एम ∞ एक छोटी मशीन हो जो हमेशा के लिए लूप हो।
फिर, (एम एम मैं, मैं, एम ∞, एम ∞) iff एम इनपुट I पर मैं हाल्ट एल में है।
इससे एल की डीसीडिबिलिटी को रोकने की समस्या की कमी हो जाती है, इसलिए एल अयोग्य है।
=============
आगे, साबित होता है कि एल रिकर्सिवली विरोधाभास से गणनीय नहीं है करते हैं।
मान लें कि एल रिकर्सिवली इन्युमरेबल है, इसलिए वहां मौजूद एक ट्यूरिंग मशीन एम ऐसी है कि अगर एम मैं, एम जे, और एम कश्मीर तीन ट्यूरिंग मशीनें जिसका संबंधित भाषाओं के बराबर नहीं कर रहे हैं, तो M होगा अंततः ट्रिपल थूकना (एम i, एम जे, एम के)।
अब एम को संशोधित करने पर विचार करें, जिसे एम कहा जाता है, जिसे एम लेने और मूल्य (एम, एम ', एम') को एल (एम ') में जोड़कर परिभाषित किया गया है। पूछने का महत्वपूर्ण सवाल यह है कि यदि (एम, एम ', एम') एल में है? खैर, अगर (एम, एम ', एम') एल में है, तो एल (एम) बराबर एल (एम ') नहीं होना चाहिए (अन्यथा यह एल में होने वाली परिभाषा में फिट नहीं होगा), इसलिए एल (एम) इसमें शामिल नहीं होना चाहिए (एम, एम ', एम') (क्योंकि यह एकमात्र संशोधन है)। इसके विपरीत, यदि (एम, एम ', एम') एल में नहीं है, तो एल (एम)! = एल (एम ') (क्योंकि हमने एल (एम') में ट्रिप जोड़ा है, इसलिए यह एल में होना चाहिए (एम), क्योंकि भाषा बराबर नहीं हैं।
इस प्रकार, हम एक विरोधाभास तक पहुंच गए हैं जिसका अर्थ है कि एम अस्तित्व में नहीं है, और इसलिए एल आवर्ती रूप से गणना योग्य नहीं है।
हू ... दिलचस्प। क्या आप कहेंगे कि यह भाषा एल आवर्ती रूप से गणना योग्य है? –
मैंने पुनरावर्ती गणना के प्रश्न को हल करने के लिए प्रतिक्रिया को अद्यतन किया। यह वास्तव में एक मजेदार समस्या थी :) –
ओह आपका समाधान बहुत रोचक है, मैं रिकर्सिव एनमेरिबिलिटी और डिकिडेबिलिटी के बारे में बहुत कुछ सीख रहा हूं।मुझे खुशी है कि आप इसके साथ मजा आए थे। मेरे पास एक सवाल है हालांकि, यदि कोई भाषा आरई नहीं है, तो क्या इसका स्वचालित अर्थ यह नहीं है कि यह अनावश्यक है? या क्या मैं कुछ न कुछ भूल रहा हूं? –
शायद सैद्धांतिक कंप्यूटर विज्ञान में स्थानांतरित हो सकता है? क्या यह होमवर्क है? –
क्या यह 'दो automatons समकक्ष' समस्या नहीं है? एनपी मुश्किल? –
मुझे लगता है कि ट्यूरिंग मशीन समतुल्यता समस्या बताती है कि भाषा बराबर होनी चाहिए? इस मामले में यह अपरिहार्य है। इस सवाल में भाषा बराबर नहीं हैं। –