लोगों को लगता है कि रोकने की समस्या को हल करना आसान है?

Question

हालांकि सामान्य मामला अपरिहार्य है, फिर भी कई लोग ऐसी समस्याओं को हल करते हैं जो दिन-प्रतिदिन उपयोग के लिए पर्याप्त समतुल्य हैं।

कंप्यूटर वायरस पर कोहेन के पीएचडी थीसिस में, उन्होंने दिखाया कि कैसे वायरस स्कैनिंग रोकथाम की समस्या के लिए समतुल्य है, फिर भी हमारे पास इस चुनौती के आसपास एक संपूर्ण उद्योग है। http://research.microsoft.com/Terminator/

मुझसे पूछते हैं की ओर जाता है कौन - -

मैं भी माइक्रोसॉफ्ट के टर्मिनेटर परियोजना देखा है हॉल्टिंग समस्या अहंकारी है - हम सामान्य स्थिति के बारे में चिंता की जरूरत है?

प्रकार समय के साथ पूरा हो जाएगा - निर्भर प्रकार अच्छे विकास की तरह लगते हैं?

या, दूसरी तरफ देखने के लिए, क्या हम स्थैतिक विश्लेषण के लाभ प्राप्त करने के लिए गैर ट्यूरिंग पूर्ण भाषाओं का उपयोग करना शुरू कर देंगे?

Answer 1

हैल्टिंग समस्या वास्तव में केवल दिलचस्प है यदि आप इसे सामान्य मामले में देखते हैं, क्योंकि अगर हलिंग समस्या क्षीण हो सकती है, तो अन्य सभी अनावश्यक समस्याएं भी कमी के माध्यम से निर्णायक हो सकती हैं।

तो, इस सवाल पर मेरी राय है, नहीं, यह महत्वपूर्ण मामलों में आसान नहीं है। उस ने कहा, असली दुनिया में, यह इतना बड़ा सौदा नहीं हो सकता है।

यह भी देखें: http://en.wikipedia.org/wiki/Halting_problem#Importance_and_consequences

Answer 2

एक दिन के लिए दिन के प्रोग्रामर के रूप में, मैं कहना चाहता हूँ यह जहाँ तक पथ नीचे हॉल्टिंग शैली समस्याओं को सुलझाने के लिए जारी रखने के लिए फ़ायदेमंद हो सकता है, भले ही आप केवल उस सीमा दृष्टिकोण और कभी नहीं पहुंचें। जैसा कि आपने बताया, वायरस स्कैनिंग मूल्यवान साबित होता है। Google खोज "मुझे वाई के लिए सर्वश्रेष्ठ एक्स ढूंढने" का पूर्ण उत्तर होने का नाटक करती है, लेकिन यह भी उपयोगी रूप से उपयोगी है। अगर मैं एक उपन्यास वायरस (मुवाहाहा) का खुलासा करता हूं, तो क्या यह एक बड़ा समाधान सेट बनाता है, या किसी मौजूदा समस्या क्षेत्र पर प्रकाश डाला जाता है? तकनीकी अंतर के बावजूद, कुछ व्यावहारिक रूप से फॉलो-अप "पहचान और निष्कासन" सेवाओं के लिए विकसित और चार्ज करेंगे।

मैं अपने अन्य प्रश्न के लिए असली वैज्ञानिक जवाब के लिए तत्पर हैं ...

Answer 3

हॉल्टिंग समस्या को हल करने के लिए आसान की तुलना में लोगों को लगता है है?

मुझे लगता है कि यह वास्तव में लोगों के विचार के रूप में मुश्किल है।

प्रकार समय के साथ पूरा हो जाएगा?

My dear, they already are!

निर्भर प्रकार एक अच्छा विकास की तरह प्रतीत होती हैं?

बहुत कुछ।

मुझे लगता है कि गैर-ट्यूरिंग पूर्ण-लेकिन-साबित भाषाओं में वृद्धि हो सकती है। कुछ समय के लिए, एसक्यूएल इस श्रेणी में था (यह अब और नहीं है), लेकिन इससे वास्तव में इसकी उपयोगिता कम नहीं हुई। मुझे लगता है कि इस तरह के सिस्टम के लिए निश्चित रूप से एक जगह है।

Answer 4

संयोग से, मुझे लगता है कि टेम्पलेट्स की ट्यूरिंग पूर्णता से पता चलता है कि रोकना अतिरंजित है। अधिकांश भाषाएं गारंटी देती हैं कि उनके कंपाइलर्स रुक जाएंगे; इतना सी ++ नहीं। क्या यह भाषा के रूप में सी ++ को कम करता है? मुझे ऐसा नहीं लगता; इसमें कई त्रुटियां हैं, लेकिन संकलित करती हैं जो हमेशा रोक नहींती हैं उनमें से एक नहीं है।

Answer 5

मुझे नहीं पता कि लोग कितना कठिन सोचते हैं, इसलिए मैं यह नहीं कह सकता कि यह आसान है या नहीं। हालांकि, आप अपने अवलोकन में सही हैं कि किसी समस्या की अनिश्चितता (सामान्य रूप से) का मतलब यह नहीं है कि उस समस्या के सभी उदाहरण अपरिहार्य हैं। उदाहरण के लिए, मैं आपको आसानी से बता सकता हूं कि while false do something जैसे प्रोग्राम समाप्त हो जाते हैं (समय और झूठी के स्पष्ट अर्थशास्त्र मानते हैं)।

आपके द्वारा वर्णित टर्मिनेटर प्रोजेक्ट जैसी परियोजनाएं स्पष्ट रूप से मौजूद हैं (और शायद कुछ मामलों में भी काम करती हैं), इसलिए यह स्पष्ट है कि सभी निराशाजनक नहीं हैं। एक प्रतियोगिता भी है (मैं हर साल विश्वास करता हूं) उन उपकरणों के लिए जो पुनर्लेखन प्रणालियों के लिए समाप्ति साबित करने का प्रयास करते हैं, जो मूल रूप से गणना का मॉडल हैं। लेकिन यह मामला है कि कई मामलों में समाप्ति को साबित करना बहुत मुश्किल है।

इसे देखने का सबसे आसान तरीका शायद किसी समस्या की तत्कालता की जटिलता पर अधिकतम अनिश्चितता को देखना है। प्रत्येक तात्कालिकता कहीं भी इस अधिकतम तक के पैमाने पर है और उच्चतम अधिकतम के साथ आप आमतौर पर यह भी मानते हैं कि तत्काल औसत भी कठिन होता है।

Answer 6

ऐसे कई कार्यक्रम हैं जिनके लिए रोकथाम की समस्या हल हो सकती है और उनमें से बहुत से कार्यक्रम उपयोगी हैं।

यदि आपके पास एक कंपाइलर था जो आपको "हल्ट्स", "रोक नहींता" या "पता नहीं" बताएगा तो यह आपको बता सकता है कि कार्यक्रम के किस हिस्से ने "हल्ट" या "डॉन" टी "स्थिति पता है। यदि आप वास्तव में एक ऐसा प्रोग्राम चाहते थे जो निश्चित रूप से रुक गया या रुक गया न हो तो आप उन "फ़ोल्डर्स" इकाइयों को ठीक से ठीक नहीं करेंगे जैसे हम संकलक चेतावनियों से छुटकारा पा सकते हैं। मुझे लगता है कि हम सभी इस बात से आश्चर्यचकित होंगे कि इस आम तौर पर असंभव समस्या को हल करने की कोशिश कितनी बार उपयोगी साबित हुई।

Answer 7

वाह, यह एक भ्रमित प्रश्न है।

पहला: हल करने की समस्या व्यावहारिक अर्थ में "समस्या" नहीं है, जैसा कि "एक समस्या जिसे हल करने की आवश्यकता है।" यह गणित की प्रकृति के बारे में एक बयान है, जो गोडेल के अपूर्णता प्रमेय के समान है।

दूसरा: तथ्य यह है कि एक आदर्श वायरस स्कैनर का निर्माण करना अचूक है (इसके कारण हैल्टिंग समस्या के बराबर होने के कारण) यही कारण है कि "इस चुनौती के आसपास एक संपूर्ण उद्योग बनाया गया है।" यदि सही वायरस स्कैनिंग के लिए एक एल्गोरिदम डिज़ाइन किया जा सकता है, तो यह केवल एक बार ऐसा करने वाला व्यक्ति होगा, और उसके बाद किसी उद्योग की आवश्यकता नहीं है। कहानी खत्म

तीसरा: एक ट्यूरिंग पूर्ण भाषा में कार्य करना "स्थिर विश्लेषण के लाभ" को खत्म नहीं करता है - इसका मतलब केवल स्थिर विश्लेषण के लिए सीमाएं हैं। यह ठीक है - वैसे भी, हम जो कुछ भी करते हैं, उसके लिए सीमाएं हैं।

अंत में: अगर किसी भी तरह से हल करने की समस्या "हल" की जा सकती है, तो यह निश्चित रूप से "लोगों के विचार से आसान" होगा, क्योंकि ट्यूरिंग ने दिखाया कि यह असफल है। गणितीय दृष्टिकोण से सामान्य मामला एकमात्र प्रासंगिक मामला है। विशिष्ट मामलों इंजीनियरिंग के मामले हैं।

Answer 8

तथ्य यह है कि एक समस्या अनावश्यक है इसका मतलब यह नहीं है कि यह दिलचस्प नहीं है: इसके विपरीत! तो हां, तथ्य यह है कि हमारे पास सभी प्रोग्राम (साथ ही सॉफ्टवेयर के बारे में कई अन्य समस्याओं) के लिए समाप्ति को संबोधित करने के लिए प्रभावी और समान प्रक्रिया नहीं है, इसका मतलब यह नहीं है कि आंशिक समाधानों की तलाश करना उचित नहीं है।एक मायने में, यही कारण है कि हमें सॉफ्टवेयर इंजीनियरिंग की आवश्यकता है: क्योंकि हम केवल कंप्यूटर को कार्य नहीं दे सकते हैं।

हालांकि, आपके प्रश्न का शीर्षक थोड़ा भ्रामक है। मैं डॉ। पिज्जा से सहमत हूं: समाप्ति समस्या वास्तव में उतनी ही मुश्किल है जितनी लोग सोचते हैं। इसके अलावा, तथ्य यह है कि हमें सामान्य मामले से चिंता करने की ज़रूरत नहीं है, यह इस बात का तात्पर्य नहीं है कि समाप्ति की समस्या खत्म हो गई है: आंशिक समाधान बीक्यूज हम जानते हैं कि सामान्य समाधान कठिन है।

अंत में, निर्भर प्रकारों और उप-भाषात्मक भाषाओं के बारे में मुद्दे, हालांकि आंशिक रूप से संबंधित, वास्तव में अलग-अलग प्रश्न हैं, और मुझे उन सभी को एक साथ मिश्रण करने के लिए बिंदु देखना नहीं है।