BB(3, 3) कठिन है

 (sligocki.com)
1 पॉइंट द्वारा GN⁺ 2023-10-19 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • यह लेख 3 स्टेट, 3 सिंबल वाली Turing machine पर चर्चा करता है, जिनके halt होने या न होने को साबित करना Collatz-जैसी समस्या को हल किए बिना संभव नहीं है; इसलिए इसमें कहा गया है कि BB(3,3) समस्या उतनी ही कठिन है जितनी उस Collatz-जैसी समस्या को हल करना।
  • लेखक Turing machines (TMs) के ऐसे एक परिवार का उल्लेख करता है जिनके quasihalt होने को साबित करने के लिए Collatz-जैसी समस्या का efficient simulation या पूर्ण समाधान चाहिए।
  • लेखक ने सामान्य Busy Beaver game से उदाहरण लिए और कई ऐसी TMs खोजीं जो Busy Beaver game के लिए परिणाम प्रदान करती हैं।
  • लेखक Bigfoot नाम की एक TM प्रस्तुत करता है, जो अनौपचारिक BB(3,3) प्रतिरोधियों में बचे हुए 160 में से एक है।
  • Bigfoot के व्यवहार को इस तरह समझाया गया है कि वह b और c पर एक Collatz-जैसे function को iterate करता है, जबकि a संचयी योग बनाए रखता है।
  • लेखक Markov chain सिद्धांत का उपयोग करके Bigfoot के व्यवहार की व्याख्या करता है और निष्कर्ष निकालता है कि Bigfoot "probviously" कभी halt नहीं होगा।
  • लेखक सुझाव देता है कि हम दो दुनियाओं में से एक में रहते हैं: एक जहाँ Bigfoot halt करता है, या दूसरी जहाँ वह हमेशा चलता रहता है; और उसका मानना है कि हम दूसरी दुनिया में रहते हैं।
  • लेखक इस तरह की machines को Cryptids कहने का प्रस्ताव रखता है, जो Loch Ness Monster या Chupacabra जैसे पौराणिक जीवों की उपमा से प्रेरित है।
  • लेखक इस समस्या पर हमला करने के तरीकों के बारे में विचार आमंत्रित करता है और आशा व्यक्त करता है कि BB(3,3) का proof अभी भी संभव है।
  • अंत में लेखक कहता है कि उसके अनुभव में Collatz-जैसी समस्याओं के बारे में पूछे जा सकने वाले सवाल मोटे तौर पर दो प्रकार के होते हैं: वे जो अपेक्षाकृत आसानी से सिद्ध हो जाते हैं, और वे जिनके प्रमाण का तरीका गणितज्ञों को भी नहीं पता।

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

1 टिप्पणियां

 
GN⁺ 2023-10-19
Hacker News की राय
  • BB(3, 3) की जटिलता पर चर्चा; यह Collatz-टाइप समस्या के रूप में जानी जाती है, लेकिन यह तर्क दिया गया कि पक्षपाती व्यवहार और केवल एकल trajectory पर विचार करना पड़ता है, इसलिए यह ज़रूरी नहीं कि कठिन ही हो।
  • 748 states वाली Turing machine पर चर्चा, जो तब halt होती है जब ZFC (Zermelo-Fraenkel set theory और axiom of choice) असंगत हो। BB(748) steps पर इस मशीन को चलाने के निहितार्थ और Gödel के second incompleteness theorem के साथ संभावित विरोधाभास को लेकर भ्रम व्यक्त किया गया।
  • लेखक की लेखन शैली की स्पष्टता और संक्षिप्तता की प्रशंसा, जिससे पाठकों को बिना अनावश्यक विस्तार के विषय समझने में मदद मिलती है।
  • यह सवाल उठाया गया कि BB (Busy Beaver) के uncomputable होने का क्या अर्थ है, और क्या BB के बढ़ने के साथ सब कुछ साबित करना ज़रूरी हो जाता है।
  • यह सुझाव कि सभी BB(x, y) समस्याओं को Collatz जैसी समस्या में reduce किया जा सकता है, और इसलिए x और y के किसी भी मान के लिए BB(x, y) खोजना भी Collatz जैसी समस्या में reduce किया जा सकता है।
  • यह सवाल कि Beeping Busy Beavers (BBB) बहुत अधिक समय तक चलने से पहले quasi-halt क्यों कर सकते हैं; यह सुझाव कि शायद इसलिए क्योंकि उन्हें halt state का उपयोग करने की आवश्यकता नहीं होती।
  • halting problem का वास्तविक दुनिया में induction पर क्या प्रभाव पड़ता है, इस पर सवाल; एक काल्पनिक परिदृश्य जिसमें एक oracle शामिल है जो यह तय कर सकता है कि दी गई Turing machine output tape पर कुछ अलग प्रिंट करेगी या नहीं।
  • इन विषयों को समझने के लिए आवश्यक prerequisite knowledge पर सवाल, और अच्छे आधार के लिए किन खास विषयों या पाठ्यक्रमों को पढ़ना चाहिए, इस पर अनुरोध।
  • एक खास string, 1RB2RA1LC_2LC1RB2RB_---2LA1LA, को कैसे पढ़ा जाना चाहिए, इस पर सवाल।