चावल प्रमेय
राइस प्रमेय में कहा गया है कि ट्यूरिंग मशीन द्वारा मान्यता प्राप्त भाषा की कोई भी गैर-तुच्छ अर्थ-संपत्ति अपरिहार्य है। एक संपत्ति, पी, सभी ट्यूरिंग मशीनों की भाषा है जो उस संपत्ति को संतुष्ट करती है।
औपचारिक परिभाषा
यदि P एक गैर-तुच्छ संपत्ति है, और संपत्ति को रखने वाली भाषा, L p , को ट्यूरिंग मशीन M से पहचाना जाता है, तो L p = {<M> | L (M)} P} अनिर्दिष्ट है।
विवरण और गुण
भाषाओं की संपत्ति, P, केवल भाषाओं का एक सेट है। यदि कोई भाषा P (L) P) से संबंधित है, तो यह कहा जाता है कि L संपत्ति P को संतुष्ट करता है।
एक संपत्ति को तुच्छ कहा जाता है यदि या तो यह किसी भी पुनरावर्ती भाषाओं द्वारा संतुष्ट नहीं है, या यदि यह सभी पुनरावर्ती भाषाओं द्वारा संतुष्ट है।
एक गैर-तुच्छ संपत्ति कुछ पुनरावर्ती भाषाओं द्वारा संतुष्ट है और दूसरों द्वारा संतुष्ट नहीं है। औपचारिक रूप से, एक गैर-तुच्छ संपत्ति में, जहां एल both पी, दोनों निम्नलिखित गुण रखते हैं:
Property 1 - ट्यूरिंग मशीन, एम 1 और एम 2 मौजूद हैं जो एक ही भाषा को पहचानते हैं, या तो (<M1>, <M2> (L) या (<M1>, <M2>) L)
Property 2 - ट्यूरिंग मशीन एम 1 और एम 2 मौजूद है, जहां एम 1 भाषा को पहचानता है जबकि एम 2 नहीं करता है, अर्थात <एम 1> <एल और <एम 2> ∉ एल
प्रमाण
मान लीजिए, एक संपत्ति P गैर-तुच्छ है और P P P है।
चूंकि, P गैर-तुच्छ है, इसलिए कम से कम एक भाषा P, अर्थात, L (M 0 ) ∋ P,, ट्यूरिंग मशीन M 0 को संतुष्ट करती है ।
बता दें, w एक विशेष इंस्टेंट में एक इनपुट है और N एक ट्यूरिंग मशीन है जो इस प्रकार है -
इनपुट x पर
- W पर M चलाएं
- यदि M स्वीकार नहीं करता है (या रुकता नहीं है), तो x स्वीकार न करें (या रोकें नहीं)
- यदि M स्वीकार करता है तो x पर M 0 चलाएं । यदि M 0 x स्वीकार करता है, तो x स्वीकार करें।
एक ऐसा फंक्शन, जो एटीएम का उदाहरण देता है = {<M, w> | M इनपुट w} को N को ऐसे स्वीकार करता है कि
- यदि M, W को स्वीकार करता है और N उसी भाषा को M 0 के रूप में स्वीकार करता है , तो L (M) = L (M 0 ) and p
- यदि M, W और N को स्वीकार नहीं करता है, तो L (N) = w। P को स्वीकार करता है
चूँकि A TM अनिर्दिष्ट है और इसे Lp में घटाया जा सकता है, Lp भी अनिर्वचनीय है।