पाँचवें Busy Beaver के साथ शोधकर्ता गणना की सीमाओं के करीब पहुँचे

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

  • परिचय

    • 40 साल पहले, जर्मनी के डॉर्टमुंड में कंप्यूटर वैज्ञानिक इकट्ठा हुए और पाँचवें Busy Beaver को खोजने की होड़ में शामिल हुए
    • Busy Beaver एक सरल कंप्यूटर प्रोग्राम है, लेकिन इसका रनटाइम बहुत लंबा हो सकता है
    • ये प्रोग्राम गणित की प्रसिद्ध अनसुलझी समस्याओं से जुड़े हैं और कंप्यूटर साइंस की एक पुरानी समस्या से निकले हैं
    • दो साल पहले, ग्रेजुएट छात्र Tristan Stérin ने Busy Beaver Challenge शुरू किया, जिसमें दुनिया भर से 20 से अधिक योगदानकर्ताओं ने भाग लिया
    • आज, टीम ने BB(5) का मान 47,176,870 के रूप में सत्यापित किया है

  • रुकेगा या नहीं रुकेगा

    • Busy Beaver प्रोग्राम एक सैद्धांतिक कंप्यूटर, जिसे Turing machine कहा जाता है, के लिए निर्देशों के रूप में लिखे जाते हैं
    • Turing machine अनंत टेप पर 0 और 1 पढ़कर-लिखकर गणना करती है
    • Turing machine रुकेगी या हमेशा चलती रहेगी, इसका अनुमान लगाने की समस्या को halting problem कहा जाता है
    • halting problem का कोई सामान्य समाधान नहीं है, और यही Busy Beaver की खोज को और आकर्षक बनाता है

  • Beaver का आगमन

    • गणितज्ञ Tibor Radó ने 1962 में Busy Beaver game का आविष्कार किया
    • हर नियम-समूह में सबसे लंबे समय तक चलने वाली Turing machine को Busy Beaver कहा जाता है
    • BB(n) उन चरणों की संख्या को दर्शाता है, जितने चरणों के बाद n नियमों वाली Busy Beaver machine रुकती है

  • Brady का Beaver समूह

    • Allen Brady ने 1960 के दशक में Busy Beaver खोज की तकनीकें विकसित कीं और 1974 में चौथे Busy Beaver का मान निर्धारित किया
    • BB(4) को ऐसी machine के रूप में पुष्टि मिली जो 107 चरणों के बाद रुकती है

  • पाँचवाँ Beaver

    • 1984 की डॉर्टमुंड प्रतियोगिता में पाँचवें Busy Beaver को खोजने के लिए पहली बड़ी खोज शुरू हुई
    • 1989 में, Heiner Marxen ने ऐसी machine खोजी जो 47,176,870 चरणों के बाद रुकती है
    • 2003 में, Georgi Georgiev ने 43 अनसुलझी Turing machines छोड़कर BB(5) की खोज रोक दी

  • सभी खोजकर्ताओं को बुलावा

    • Tristan Stérin ने 2022 में Busy Beaver Challenge शुरू किया, जिसमें दुनिया भर के योगदानकर्ता शामिल हुए
    • Shawn Ligocki 2022 में टीम में शामिल हुए और उन्होंने महत्वपूर्ण योगदान दिए
    • Justin Blanchard ने टीम की सबसे शक्तिशाली तकनीकों में से एक, closed tape language method, विकसित की

  • दानव के करीब पहुँचना

    • Skelet #1 और #17 खास तौर पर कठिन machines थीं, और टीम ने उन्हें हल करने के लिए कई विचारों को जोड़ा
    • मई 2023 में, mxdys नामक एक अनाम योगदानकर्ता ने Coq proof पूरा किया

  • जहाँ Beaver घूमते हैं

    • टीम एक औपचारिक अकादमिक पेपर लिख रही है, और कुछ सदस्य अगले Beaver को खोजने की कोशिश कर रहे हैं
    • BB(6) को Collatz conjecture जैसी समस्या के कारण हल करना कठिन लगता है

GN⁺ की राय

  • यह लेख कंप्यूटर साइंस की सीमाओं की पड़ताल करने वाला एक दिलचस्प उदाहरण प्रस्तुत करता है
  • Busy Beaver Challenge सहयोगी शोध के महत्व को दिखाता है
  • BB(5) का समाधान कंप्यूटर साइंस और गणित समुदाय, दोनों के लिए बड़ा महत्व रखता है
  • समान प्रकृति वाले प्रोजेक्ट्स में Collatz conjecture पर शोध शामिल है
  • नई तकनीक या open source अपनाते समय सहयोग और reproducibility महत्वपूर्ण हैं

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

1 टिप्पणियां

 
GN⁺ 2024-07-03
Hacker News टिप्पणियाँ

  • Scott Aaronson की ब्लॉग पोस्ट पर टिप्पणियाँ साझा की गईं

    • संबंधित पुराने थ्रेड का लिंक दिया गया है

  • Busy Beaver समस्या के कई अलग-अलग variants मौजूद हैं

    • lambda calculus का उपयोग करने वाला एक variant है
    • Kolmogorov complexity में व्यक्त किया जाने वाला एक variant है

  • एक engineer द्वारा Busy Beaver समस्या का अध्ययन करने के लिए नौकरी छोड़ने की कहानी साझा की गई

    • यह जिज्ञासा जताई गई कि क्या वह engineer mxdys है

  • Coq proof का उल्लेख है

    • यह संभावना जताई गई कि यह शुरू से व्यवस्थित किया गया proof नहीं, बल्कि पहली बार व्यवस्थित किया गया proof हो सकता है

  • Tibor Radó का मूल Busy Beaver paper पढ़ने में आसान और दिलचस्प होने की राय व्यक्त की गई

    • paper के आधुनिक version का लिंक दिया गया है

  • 5-state 2-color Turing machine programs के halting problem का समाधान किया गया है

    • यह संभावना उठाई गई कि क्या इसे 2-state 4-color मामले पर लागू किया जा सकता है

  • इस गलत धारणा का उल्लेख है कि मनुष्य halting problem को सहज रूप से हल कर सकते हैं

  • एक निजी project में Cutting Stock समस्या हल करने के लिए program लिखने का अनुभव साझा किया गया

    • Brady के program जैसी optimization method का उपयोग किया गया

  • यह राय दी गई कि 5-state Turing machine programs के halt होने या न होने को साबित कर पाना सौभाग्य की बात थी

  • Scott Aaronson की ब्लॉग पोस्ट के अनुसार 16,679,880,978,201 5-state Turing machines मौजूद हैं

    • इनमें से कितने प्रतिशत halt करते हैं, इस पर जिज्ञासा जताई गई

  • Busy Beaver function के मान साझा किए गए

    • BB(5) के 47,176,870 होने का proof दिया गया
    • BB(6) कम से कम 10^10^...^10 (15 स्तरों वाली exponent tower) है