2010-10-12 20 views
7

गणना सिद्धांत में शर्तें लागू और निर्णायक अंतर परिवर्तनीय हैं? क्या उनका मतलब एक ही बात है?प्रोवबल == अनुमानित है?

उदाहरण के लिए आप अक्सर सवाल देखते हैं कि कुछ निर्णय साबित करने योग्य है (दास एंट्सिडुंग्सप्रोबलेम)।

+1

शायद mathoverflow.net के लिए एक उपयुक्त सवाल है? –

+2

मैंने इसके बारे में सोचा लेकिन कॉम्प के रूप में। थ्योरी (और जटिलता) पाठ्यक्रम लगभग सभी सीएस \ एसई पाठ्यक्रमों पर पाया जा सकता है, मैंने सोचा कि यहां अधिक उपयुक्त होगा। –

उत्तर

1

ये अलग हैं। वास्तव में, वे पूरी तरह से अलग क्षेत्रों का संदर्भ लें।

निर्णय लेने योग्य साधन, कि ट्यूरिंग मशीन द्वारा सभी संभावित इनपुट के लिए निर्णय समस्या हल की जा सकती है, जो 'स्वीकार' या 'अस्वीकार' करती है।

प्रबल माध्यम का अर्थ है कि गणितीय विवरण, गणितीय प्रमाण से भी सिद्ध किया जा सकता है।

वास्तव में, आप 'decidable' और 'provable' की तुलना नहीं कर सकते, क्योंकि ये विशेषताएं पूरी तरह से अलग-अलग चीजों का संदर्भ देती हैं।

+0

आपको साबित करना होगा कि मशीन का निर्णय ठीक से काम करता है;) – Dario