BusyBeaver(6) वाकई बहुत बड़ा है

• Busy Beaver की छठी संख्या (BB(6)) की निचली सीमा हाल की नई रिसर्च से बहुत बढ़ गई है
• पहले BB(6) > 10↑36,534 माना जाता था, लेकिन 2022 में इसे बढ़ाकर BB(6) > 10↑1510 किया गया
• हाल में BBchallenge में इसे फिर बढ़ाकर BB(6) > 10↑10,000,00010 किया गया, और उसके बाद 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) तक अपडेट किया गया
• BB(6) का आकार कल्पना से परे है, और यह संख्या पूरे ब्रह्मांड को अनगिनत बार भर देने जितनी विशाल है
• यह प्रगति गणितीय तर्क और computation theory की सीमाओं और संभावनाओं को नए ढंग से समझने का अवसर देती है

---

BB(6) पर हालिया शोध उपलब्धियों का अवलोकन

• पिछले कुछ वर्षों से दुनिया और शोध का माहौल लगातार कठिन महसूस हो रहा था
• लेकिन Busy Beaver रिसर्च में यह प्रगति शोध के प्रति शुद्ध उत्साह को फिर याद दिलाने का अवसर बनी
• 2022 में Pavel Kropitz ने प्रमाणित किया कि BB(6) > 10↑1510
  • BB(6) का मतलब है कि 6 states वाली Turing machine all-zero tape पर रुकने से पहले अधिकतम कितने steps चला सकती है
  • यहाँ ^1510 का अर्थ है 10 का 15 बार self-repeated exponentiation, यानी tetration
• पहले के शोध में BB(5) का मान 47,176,870 बताया गया था (BBchallenge टीम), और यही वह बिंदु है जहाँ यह संख्या observable reality की सीमा से बाहर के क्षेत्र में तेजी से पहुँचने लगती है

हालिया lower-bound अपडेट की प्रक्रिया

• BBchallenge के "mxdys" ने प्रमाणित किया कि BB(6) > 10↑10,000,00010
  • यह प्रमाण Coq भाषा में लिखे गए formal proof पर आधारित है
• इसके बाद lower bound को फिर BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) तक अपडेट किया गया
  • ↑↑ का अर्थ tetration, यानी exponentiation की पुनरावृत्ति, और यहाँ 2 को 2 से tetration करके, फिर उस परिणाम पर tetration को 9 बार दोहराने जैसा रूप है
  • इस स्तर की संख्या किसी भी मौजूदा intuitive understanding से परे है
• संदर्भ के लिए, pentation tetration की पुनरावृत्ति है, और यह multiplication, exponentiation, tetration से भी आगे की operation है

बहुत बड़ी संख्याओं के आकार को समझना

• एक पत्रकार के अनुरोध पर 10↑10,000,00010 जैसी संख्या का आकार समझाना आवश्यक था
• यह संख्या इतनी बड़ी है कि उतने ब्रह्मांडों को रेत से भरा जा सकता है: 10↑10,000,00010
• इससे यह बात सामने आती है कि BB(6) का मान वास्तविक observable world से बहुत, बहुत आगे है

BB algorithm की मूलभूत सीमाओं पर विचार

• BB(6) के असाधारण आकार से Busy Beaver function की वास्तविक क्षमता दिखाई देती है
• अनुमान था कि वह बिंदु जहाँ BB(n) का मान set theory (ZFC) की axiom system से independent हो जाता है, शायद n=20~30 के आसपास होगा, लेकिन अब लगता है कि n=7~9 पर भी यह स्वतंत्र हो सकता है
  • अभी औपचारिक रूप से n=643 पर independence ज्ञात है

परिशिष्ट: हालिया कार्यक्रम और व्याख्यान समाचार

• लेखक ने हाल में Prague में आयोजित STOC'2025 कार्यक्रम में भाग लिया, जहाँ विभिन्न शोधकर्ताओं से संवाद हुआ और नई जानकारी मिली
• अपने quantum speedup status पर keynote lecture slides भी साझा किए
• इस विषय पर अधिक विस्तृत अनुभव-लेख बाद में साझा करने की योजना है

[GN⁺]

Hacker News राय

• bbchallenge Discord सर्वर में लोगों ने यह अनुमान साझा किया कि Graham's Number को पार करने के लिए कितनी Turing machine states चाहिए होंगी। हाल का BB(6) विजेता 2^^2^^2^^9 तक पहुँच चुका है, जो अपने आप में ही बेहद विशाल संख्या है, लेकिन यह देखकर हैरानी हुई कि Graham जैसी growth उम्मीद से कहीं जल्दी सामने आ सकती है। functional busy beaver [1] सामग्री का हवाला दिया गया, जिसमें कहा गया है कि सिर्फ 49-bit lambda term भी पर्याप्त हो सकता है, और उस आकार के closed lambda terms केवल 77519927606[2] हैं, जबकि 6-state Turing machines की संख्या 399910780272640[3] है। 6 states में pentation implement हो जाने के बाद अब काफ़ी लोग मानते हैं कि 7 states Graham's Number को भी पार कर सकती हैं। फिर भी लेखक को यह अब भी अप्रत्याशित लगता है। कुछ दिन पहले उन्होंने इस पर बड़ी शर्त लगाई कि अगले 10 साल में BB(7) के Graham's Number से बड़ा होने का प्रमाण आ जाएगा या नहीं, और दूसरों की राय पूछी। (1, 2, 3 लिंक दिए गए हैं)
  • मैं विशेषज्ञ होने का दावा नहीं करूँगा, लेकिन मेरा अनुमान है कि BB(7), Graham's Number से बड़ा होगा। BB को किसी भी computable sequence से तेज़ बढ़ना चाहिए, इसलिए BB(7) वास्तव में कितना बड़ा है यह अभी बस मोटा अंदाज़ा ही है, लेकिन दिशा यही है कि अंततः यह हर computable operator (जैसे up-arrow^n आदि) से भी तेज़ बढ़े। 47176870 से 2^^2^^2^^9 तक की छलांग, 2^^2^^2^^9 से Graham's Number तक की छलांग की तुलना में operator strength के लिहाज़ से कहीं ज़्यादा नाटकीय लगती है। Graham's Number, g_64 है, और इसे भी up-arrow^n से एक स्तर ऊपर की अवधारणा माना जा सकता है, इसलिए सहज अनुमान यही है कि BB(7), Graham's Number को पार कर जाएगा।
• यह बात बेहद चौंकाने वाली लगी कि BB(748) जैसी uncomputable संख्या ZFC (set theory axiom system) से independent है। ईमानदारी से कहें तो यह लगभग category error जैसा महसूस होता है।
  • BB(748) के ZFC से independent होने का कारण उसका मान स्वयं नहीं, बल्कि यह है कि 748 states में से एक TM_ZFC_INC इस तरह बनाया गया है कि वह तभी halt करता है जब उसे ZFC में contradiction (गलत proof) मिल जाए। BB(748)=N साबित करने के लिए यह दिखाना होगा कि TM_ZFC_INC N steps के भीतर halt करता है या हमेशा चलता रहता है; Gödel के incompleteness theorem के अनुसार, यदि ZFC consistent है, तो यह implication ZFC के भीतर साबित नहीं की जा सकती।
  • इससे भी अधिक आश्चर्यजनक यह लगता है कि कुछ पंक्तियों का text, यानी ZFC axioms स्वयं, मनुष्यों के लिए महत्वपूर्ण arithmetic truths को पर्याप्त रूप से व्यक्त कर सकते हैं। 6-state Turing machine के व्यवहार का आसानी से अनुमान न लगा पाना तो स्वाभाविक है। अफ़सोस यह है कि Gödel के incompleteness theorem के बाद गणित जगत को और axioms खोजने की दिशा में काफ़ी सक्रिय होना चाहिए था, लेकिन वास्तव में यह काम सिर्फ़ कुछ foundational research तक सीमित रह गया।
  • continuum hypothesis का truth value (यदि कोई platonist दृष्टिकोण ले तो 1 या 0) ZFC से independent होना इसका अच्छा उदाहरण है। कोई विशाल संख्या नहीं, सिर्फ़ 1 bit भी ZFC से guaranteed नहीं है।
  • यह स्पष्ट अंतर है कि BB(n) uncomputable है, जबकि BB(748) परिभाषा के अनुसार 748-state Turing machine द्वारा लिखे गए 1s की एक गिनती है, इसलिए वह computable संख्या है। "independent" लेबल का मतलब यह है कि यह साबित करने की प्रक्रिया कि यह संख्या वास्तव में वही वांछित मान है, उसके लिए ZFC से अधिक शक्तिशाली theory की ज़रूरत पड़ती है।
  • यह संख्या स्वयं ZFC से independent नहीं है; BB(748) को compute करने की प्रक्रिया independent है। (हर integer को ZFC में व्यक्त किया जा सकता है)
• यह एक प्रसिद्ध तथ्य है कि BB(14), Graham's Number से बड़ा है, और इस शोध के बाद सहज लगता है कि BB(7) भी Graham's Number से कम से कम बड़ा या बराबर होगा। अंतर्ज्ञान से देखें तो pentation से Graham's Number तक पहुँचना, 47,176,870 से 2 <pentate> 5 तक पहुँचने की तुलना में शायद और भी सरल विचार है।
  • बढ़िया जानकारी, यह मेरी पोस्ट के लिए एक उत्कृष्ट जवाब हो सकता है।
• Scott Aaronson का “How Much Math Is Knowable?” [Harward CMSA] YouTube व्याख्यान https://www.youtube.com/watch?v=VplMHWSZf5c और हाल की HN चर्चा https://news.ycombinator.com/item?id=43776477 साझा की गई।
• बताया गया कि "ऊपर-बाएँ superscript" tetration है, यानी repeated exponentiation। ¹⁵10 का मतलब है 10 की 10 की... कुल 15 बार पुनरावृत्ति। यह अवधारणा पहली बार देखी, तो पहले लगा कोई typo है।
  • repeated operations की उसी थीम में आगे बढ़ते हुए, इस बार ‘pentation’ पहली बार देखने की प्रतिक्रिया दी गई।
  • tetration पहले देखी थी, लेकिन Knuth की up-arrow notation[1] ज़्यादा सामान्य और generalization के लिए बेहतर लगती है। (1)
• BB(6) की यह व्याख्या कि यह 6-state, 2-symbol ({0,1}) Turing machine के लिए, शुरू में all-0 tape से halt करने से पहले लिए गए maximum steps की संख्या है, non-experts के लिए बहुत उपयोगी लगी। इससे एहसास हुआ कि यह क्षेत्र दशकों से शोध कर रहे लोगों के लिए बहुत dense और specialized terminology वाला है, लेकिन संयोग से इतना गहरा लेख पढ़ने को मिला, यह अच्छा लगा।
  • मेरा मानना है कि अगर कोई computer science undergraduate स्तर का छात्र हो, तो busy beaver problem पहली बार देखने पर भी एक सामान्य समझ बना सकता है। हाँ, विशेष शब्द बहुत हैं, लेकिन इसे केवल दशकों के अनुभव वालों के लिए ही समझना ज़रूरी नहीं मानना चाहिए।
  • यह भी स्पष्ट किया गया कि यह definition software engineering की तुलना में theoretical computer science में standard है।
• इस बात से उलझन हुई कि अगर "10,000,000 sub10" रेत के कण हों, तो observable universe को 10,000,000 sub10 गुना भरा जा सकता है। आम तौर पर तुलना observable universe के mass से की जाती है, और इस तरह का वर्णन तो पहले से ही वास्तविक पदार्थ की मात्रा से बहुत आगे निकल जाता है।
  • जवाब मिला: सही है। चाहे इसे रेत के कणों/ब्रह्मांड से भाग दें, संख्या फिर भी लगभग उसी स्तर की विशाल बनी रहती है; इस notation में पास-पास की संख्याओं में भी भारी अंतर होता है। 10↑↑10,000,000 / (रेत के कण/ब्रह्मांड) भी 10↑↑9,999,999 से बहुत बड़ा है। हमारी प्रणाली में (बहुत बड़ा) / (ब्रह्मांडीय रूप से बड़ा) भी बस (बहुत बड़ा) ही रहता है।
  • tetration में अब सिर्फ़ digits की संख्या नहीं, बल्कि "digits की संख्या की भी digits" जैसी growth होती है।
  • फिर दोहराया गया कि इस संख्या को 10^100000 रेत के कणों से भी व्यावहारिक रूप से कम नहीं किया जा सकता, इसलिए भाग देने से कोई सार्थक असर नहीं पड़ता।
  • उदाहरण दिया गया कि 10,000,000^10,000,000 भी पहले से हास्यास्पद रूप से बड़ा है, और उसमें एक और exponent tail जोड़ देने के बाद तुलना ही अर्थहीन हो जाती है।
  • एक अधिक परिचित उदाहरण के रूप में कहा गया कि significant figures की दृष्टि से 1 billion - 1 million = 1 billion कहना कोई बड़ी अतिशयोक्ति नहीं है।
• जिज्ञासा जताई गई कि 5-state Turing machine से proof enumeration करने योग्य logical systems में सबसे "समृद्ध" कौन-सा होगा।
  • इसका उत्तर इस पर निर्भर करेगा कि 'enumeration' को किस अर्थ में परिभाषित किया जाता है। इससे जुड़ा एक प्रश्न यह भी है: "सबसे शक्तिशाली logical system कौन-सा है जो 5-state Turing machines के halting behavior को पूरी तरह साबित नहीं कर सकता?" निजी राय यह दी गई कि Skelet #17 [0] के non-halting को गणितीय रूप से साबित करना बेहद कठिन है, इसलिए यदि कोई theory इसे सिद्ध कर दे, तो शायद बाकी सभी 5-state Turing machines को भी decide किया जा सके। (0, 1)
  • पहले यह स्पष्ट करना होगा कि finite binary strings को logical proofs की enumeration के रूप में किस तरह interpret किया जा रहा है, तभी इस premise पर सही चर्चा हो सकती है।
• यह सवाल पूछा गया कि क्या observable universe, BB(6) का exact value लिखने के लिए पर्याप्त बड़ा है।
  • यदि observable universe को एक closed system माना जाए, तो Bekenstein bound के आधार पर इसकी information storage limit लगभग 10^120 bits के आसपास आती है। वर्तमान अनुमान के अनुसार कुल mass-energy लगभग 10^53kg है, और इसे formula में रखने पर भी परिणाम लगभग 10^120 bits ही आता है। इसलिए यह संभव नहीं है।
  • ज़ोर देकर कहा गया कि ब्रह्मांड में संग्रहीत की जा सकने वाली सूचना लगभग 10^120 bits है, और यदि इसमें कई orders of magnitude की भी गलती हो, तब भी कोई फ़र्क नहीं पड़ता—यह स्पष्ट रूप से अपर्याप्त है।
  • शायद प्रश्न यह मानकर पूछा गया था कि पूरी value एक साथ store करनी होगी। यदि simultaneous storage की शर्त न हो, तो अनंत समय में सैद्धांतिक रूप से दर्ज करना संभव हो सकता है, लेकिन फिर heat death जैसी वास्तविक सीमाएँ सामने आएँगी। CMB reference frame में यह असंभव है, हालाँकि शायद कोई अलग spacetime slicing सोची जा सकती है।
  • लेख की पहली संख्या ही ¹⁵10 है, यानी 10^(¹⁴10) के रूप में, और उसके digits की संख्या ही ¹⁴10 है, इसलिए यह बिल्कुल असंभव है।
  • संक्षेप में फिर कहा गया: नहीं, संभव नहीं।
• हर बार जब computational complexity theory के ऐसे परिणाम दिखते हैं, तो यह एहसास होता है कि "superintelligence ही ईश्वर है" जैसी लोकप्रिय बातें पूरी तरह बेबुनियाद हैं। ब्रह्मांड के हर atom को supercomputer में बदल दें और black hole की energy भी इस्तेमाल कर लें, तब भी BB(6) का halting status compute करना हमेशा असंभव रहेगा।
  • संक्षिप्त प्रतिक्रिया: ऐसा strawman तर्क शुरू से ही प्रभावी नहीं था।