सैद्धांतिक कंप्यूटर विज्ञान की ज़ॉम्बी गलतफहमी

 (scottaaronson.blog)
1 पॉइंट द्वारा GN⁺ 2024-07-11 | 1 टिप्पणियां | WhatsApp पर शेयर करें

सैद्धांतिक कंप्यूटर विज्ञान की ज़ॉम्बी गलतफहमी

परिचय

  • Michael Sipser की पाठ्यपुस्तक "Introduction to the Theory of Computation" में एक बेहतरीन अभ्यास है
  • अभ्यास: "यदि कोई फ़ंक्शन f:{0,1}*→{0,1} ईश्वर के अस्तित्व के आधार पर 1 या 0 लौटाता है, तो क्या f computable है?"
  • उत्तर: "हाँ, f computable है" (क्योंकि constant function computable होते हैं)

computability की अवधारणा

  • computability फ़ंक्शनों या अनंत sequence पर लागू होती है
  • यह किसी एकल yes/no प्रश्न या किसी एकल integer पर लागू नहीं होती
  • प्रोग्राम लिखने की कठिनाई का computability से कोई संबंध नहीं है

P बनाम NP समस्या

  • P बनाम NP समस्या एक एकल yes/no प्रश्न है
  • NP-hardness फ़ंक्शनों या languages पर लागू होती है
  • P बनाम NP समस्या न तो uncomputable हो सकती है और न ही NP-hard

Busy Beaver फ़ंक्शन

  • Busy Beaver फ़ंक्शन uncomputable है
  • BB(6) जैसा कोई एकल integer computable है
  • पूरा BB फ़ंक्शन uncomputable है

सैद्धांतिक कंप्यूटर विज्ञान की ज़ॉम्बी गलतफहमी

  • फ़ंक्शनों और अनंत sequence पर लागू होने वाली अवधारणाओं को गलत तरीके से एकल integer और खुले प्रश्नों पर लागू करना
  • halting problem की uncomputability और Gödel incompleteness को आपस में भ्रमित करना

पाठकों से प्रश्न

  • पाठकों से पूछा गया है कि इस ज़ॉम्बी गलतफहमी को कैसे रोका जा सकता है

GN⁺ का सार

  • यह लेख सैद्धांतिक कंप्यूटर विज्ञान में बार-बार होने वाली गलतफहमियों पर चर्चा करता है
  • computability फ़ंक्शनों या अनंत sequence पर लागू होती है, न कि एकल integer या yes/no प्रश्नों पर
  • P बनाम NP समस्या एक एकल प्रश्न है, इसलिए उसका NP-hardness की अवधारणा से कोई संबंध नहीं है
  • Busy Beaver फ़ंक्शन uncomputable है, लेकिन उसके अलग-अलग मान computable हैं
  • यह लेख सैद्धांतिक कंप्यूटर विज्ञान की बुनियादी अवधारणाओं को स्पष्ट रूप से समझने में मदद करेगा

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-07-11
Hacker News राय

  • Kolmogorov complexity की गणना करने वाले algorithm के अस्तित्व का सवाल अनंतता से जुड़ा है

    • मनमानी लंबाई वाली string की Kolmogorov complexity की गणना करने वाला algorithm मौजूद नहीं है
    • लेकिन n से छोटी लंबाई वाली strings की Kolmogorov complexity की गणना करने वाला algorithm मौजूद है
    • यह सभी संभावित strings के लिए एक विशाल lookup table बनाकर संभव है
    • सीमित समस्या को हमेशा program से हल किया जा सकता है, लेकिन अनंत समस्या को नहीं

  • यह राय कि constructive mathematics लोगों की intuition से बेहतर मेल खाती है

    • P=NP समस्या के लिए कोई program मौजूद है, इसका अभी तक कोई प्रमाण नहीं है
    • Mark Braverman ने साबित किया कि सभी (quadratic) Julia sets computable हैं, लेकिन यह uniformly computable नहीं है
    • constructive mathematics में complex plane को कई क्षेत्रों में बाँटकर यह साबित किया जाता है कि हर क्षेत्र के भीतर Julia set compact है

  • halting problem की undecidability को समझना कठिन क्यों है

    • "return true" और "return false" programs में से एक हमेशा सही उत्तर देता है
    • decidability केवल तब undecidable बनती है जब उसे अनंत machine/input combinations तक बढ़ाया जाता है

  • modal logic की ज़रूरत वाले प्रश्नों की अभिव्यक्ति

    • "क्या f computable है?" यह सवाल modal दृष्टि से गलत है
    • "क्या f computable हो सकता है?" यह सवाल अधिक सटीक है
    • यह compiler directives या pragma के समान है

  • function f की भ्रमित करने वाली अभिव्यक्ति

    • function f "God exists" के मान के आधार पर branch नहीं करता
    • f चाहे 0 हो या 1, computable है
    • भ्रम free variable को branching condition में धकेलने से पैदा होता है

  • decidability, computability, existence आदि के अर्थों में अंतर

    • शैक्षणिक संदर्भ और रोज़मर्रा के संदर्भ में इनके अर्थ अलग होते हैं
    • बड़े numbers शैक्षणिक रूप से exist करते हैं और computable हैं, लेकिन व्यवहार में वे ब्रह्मांड में समा नहीं सकते

  • "God exists" से जुड़े प्रश्न की समस्या

    • यह स्पष्ट नहीं है कि "God exists" true है या false
    • यह natural language और mathematics को मिलाने पर पैदा होने वाली समस्या है

  • theory of computation और complexity theory CS undergraduates के लिए कठिन क्यों हैं

    • NP-hard जैसे terms को लोकप्रिय उपमाओं और कल्पना से बदल दिया जाता है

  • blog के text highlighting तरीके पर असंतोष

    • चुने गए text का background color नहीं बदलता, इसलिए यह intuitive नहीं लगता

  • "God exists" को किसी दूसरे mathematical proposition से बदलने का प्रस्ताव

    • "God exists" को true या false के रूप में स्पष्ट रूप से परिभाषित किया जाना चाहिए