भाषा की स्थिरता

एक भाषा कहलाती है Decidable या Recursive अगर कोई ट्यूरिंग मशीन है, जो हर इनपुट स्ट्रिंग पर स्वीकार और हॉल्ट करती है w। हर निर्णायक भाषा ट्यूरिंग-स्वीकार्य है।

एक निर्णय समस्या P यदि भाषा में निर्णायक है L के सभी हाँ उदाहरण के लिए P निर्णायक है।

प्रत्येक इनपुट स्ट्रिंग के लिए एक निर्णायक भाषा के लिए, TM निम्नलिखित चित्र में दिखाए अनुसार स्वीकार या अस्वीकार की स्थिति में रुकता है -

उदाहरण 1

यह पता करें कि निम्नलिखित समस्या विकट है या नहीं -

क्या कोई संख्या 'm' अभाज्य है?

समाधान

अभाज्य संख्या = {2, 3, 5, 7, 11, 13, ………… ..}

संख्या को विभाजित करें ‘m’ '2 ’और startingm’ के बीच की सभी संख्याओं को' 2 'से शुरू करना।

यदि इनमें से कोई भी संख्या शेष शून्य का उत्पादन करती है, तो यह "अस्वीकृत राज्य" में चला जाता है, अन्यथा यह "स्वीकृत स्थिति" में चला जाता है। तो, यहाँ उत्तर 'हां' या 'नहीं' द्वारा बनाया जा सकता है।

Hence, it is a decidable problem.