BusyBeaver(6) सचमुच बहुत बड़ा है

 (scottaaronson.blog)
2 पॉइंट द्वारा GN⁺ 2025-06-29 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • BB(6) की ज्ञात lower bound फिर से बहुत बढ़ गई है, जिससे यह पुष्टि हुई है कि 6-state Turing machine का maximum halting time देखने योग्य वास्तविकता के पैमाने से कहीं आगे की संख्या है
  • BB(6) का मतलब है: 0 से भरी tape से शुरू होने वाली 6-state·2-symbol Turing machine रुकने से पहले अधिकतम कितने steps तक चल सकती है
  • 2022 में Pavel Kropitz के सुधार के बाद, mxdys ने lower bound को फिर से 10 को 1 करोड़ बार repeated exponentiation करने से बनी संख्या से भी बड़े स्तर तक पहुँचा दिया
  • नवीनतम नतीजा दिखाता है कि BB(6) कम से कम 2 pentated to 5 है, यानी repeated exponentiation से एक स्तर ऊपर का operation भी सामने आ गया है
  • BB(5) को 47,176,870 तय किया जा चुका है, लेकिन BB(6) इतना विशाल हो गया है कि यह अनुमान मजबूत होता है कि BB(n) के ZFC axiom system से independent होने की सीमा n=7, 8, 9 पर हो सकती है

BB(6) की lower bound फिर से बढ़ी

  • 2022 से पहले BB(6) के बारे में केवल लगभग BB(6) > 10^36,534 ही ज्ञात था, और Pavel Kropitz ने इसे सुधारकर 10 को 15 बार repeated exponentiation करने से बनी संख्या से भी बड़े स्तर तक पहुँचाया
  • Tetration का मतलब repeated exponentiation है
    • उदाहरण के लिए, 10 को 15 बार stacked करने वाली संख्या वह है जिसमें 10 के 10 के 10 के … जैसा रूप 15 बार चलता है
  • BBchallenge के आयोजक Tristan Sterin ने बताया कि टीम सदस्य mxdys ने BB(6) की lower bound फिर से बढ़ा दी है
    • पहला सुधार: BB(6) > 10 को 1 करोड़ बार repeated exponentiation करने से बनी संख्या
    • इस नतीजे के लिए Coq correctness proof मौजूद है
  • mxdys के बाद के सुधार ने दिखाया कि BB(6) कम से कम 2 tetrated to 2 tetrated to 2 tetrated to 9 है
    • खास तौर पर, BB(6) कम से कम 2 pentated to 5 है
    • Pentation repeated tetration है; यह tetration द्वारा exponentiation को repeat करने से एक स्तर ऊपर का operation है

BB(5) और BB(6) के बीच चरम अंतर

  • BB(6) छठा Busy Beaver number है
    • यह 6-state Turing machines के लिए है
    • alphabet {0,1} है
    • input tape शुरुआत में पूरी तरह 0 होती है
    • इसका अर्थ है रुकने से पहले संभव अधिकतम execution steps की संख्या
  • अंतरराष्ट्रीय BBchallenge टीम ने पिछले साल BB(5) को 47,176,870 तय किया
  • BB(5) से BB(6) पर जाते ही Busy Beaver function करोड़ों के स्तर से छलांग लगाकर देखने योग्य वास्तविकता की सीमा से परे के आकार तक पहुँच जाता है

ऐसी संख्या जिसके आकार का अंदाजा लगाना लगभग नामुमकिन है

  • जब BB(6) > 10 को 1 करोड़ बार repeated exponentiation करने से बनी संख्या वाला स्तर ही था, तब भी इसे intuitively समझाना लगभग असंभव था
  • उदाहरण के लिए, तुलना में कहा गया कि अगर इतने रेत के कण हों, तो उनसे देखने योग्य ब्रह्मांड की लगभग उतनी ही प्रतियाँ भरी जा सकती हैं
  • यह तुलना दिखाती है कि यह संख्या 10^100 जैसी ब्रह्मांडीय पैमाने की संख्याओं से भी इतनी ज्यादा बड़ी है कि उनसे divide करने पर भी मूल संख्या के लगभग समान पैमाने की ही रहती है

ZFC independence के अनुमान कम हो सकते हैं

  • BB(6) के इतना बड़ा हो जाने का मतलब यह नहीं कि Busy Beaver function के बारे में सारी सोच बदल गई है
  • BB(6) के 10^36,534 जैसे अपेक्षाकृत छोटे स्तर पर न होकर iterated operations के क्षेत्र में होने की संभावना पहले से खुली थी
  • अब जब वास्तविक lower bound उसी पैमाने की पुष्टि कर रही है, तो BB(n) के मान के ZFC set theory axiom system से independent होने की सीमा पर अनुमान कम हो सकते हैं
    • पहले n=20 या 30 के आसपास सोचा जा सकता था
    • अब माना जा रहा है कि यह n=7, 8, 9 भी हो सकता है
  • फिलहाल ज्ञात ZFC independence result यह है कि BB(n), n=643 पर ZFC से independent हो जाता है

अलग अपडेट: STOC 2025

  • Prague में आयोजित STOC 2025 में कई शोधकर्ताओं से मुलाकात हुई और नई बातें जानने को मिलीं
  • STOC plenary lecture का शीर्षक The Status of Quantum Speedups है
  • रुचि रखने वाले पाठक उस lecture की PowerPoint slides देख सकते हैं

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

1 टिप्पणियां

 
GN⁺ 2025-06-29
Hacker News की राय

  • bbchallenge Discord सर्वर पर इस बात पर काफ़ी अटकलें चल रही हैं कि नए BB(6) चैंपियन द्वारा हासिल किए गए 2^^2^^2^^9 से कहीं बड़े Graham's Number को पार करने के लिए Turing machine में कितनी states चाहिए होंगी
    functional busy beaver https://oeis.org/A333479 देखें तो Graham स्तर का व्यवहार आश्चर्यजनक रूप से जल्दी दिखाई दे सकता है। 49-bit lambda term काफ़ी है
    उस size या उससे कम के closed lambda terms सिर्फ़ 77,519,927,606 हैं https://oeis.org/A114852, जबकि unique 6-state Turing machines 4^12*23836540=399910780272640 हैं https://oeis.org/A107668
    जब 6 states से ही pentation हासिल हो गई है, तो अब कई लोग मानते हैं कि 7 states Graham's Number को पार कर सकती हैं। फिर भी मुझे यह अब भी काफ़ी हैरान करने वाली बात लगती है। कुछ दिन पहले उनमें से एक के साथ मैंने इस पर बड़ा दांव लगाया कि अगले 10 साल में BB(7)>Graham's का proof आएगा या नहीं; जानना चाहूंगा कि बाकी लोग क्या सोचते हैं

    • मैं खुद को expert नहीं कह सकता, लेकिन BB(7) शायद Graham's Number से बड़ा होगा
      BB को किसी भी computable sequence से तेज़ बढ़ना चाहिए। BB(7) के लिए इसका ठोस मतलब क्या है, यह आखिरकार थोड़ा हाथ हिलाकर समझाने जैसा है, लेकिन ऐसा लगता है कि इसे operator strength की सीढ़ी बहुत तेज़ी से चढ़नी होगी। आखिरकार इसे हमारे द्वारा define किए जाने वाले किसी भी computable operator से तेज़ बढ़ना होगा, जिसमें जैसे up-arrow^n या किसी computable function f के लिए up-arrow^f(n) भी शामिल हैं
      सहज रूप से, 47 million से 2^^2^^2^^9 तक की growth, operator strength के लिहाज़ से 2^^2^^2^^9 से Graham's Number तक की growth की तुलना में गुणात्मक रूप से ज़्यादा बड़ी लगती है। Graham's Number g_64 है, जहां g मोटे तौर पर up_arrow^n से एक स्तर ऊपर है, इसलिए शायद BB(7)>Graham's Number होने की संभावना बड़ी है

  • BB(748) जैसी संख्या, वह भी non-computable संख्या, “ZFC से independent” हो सकती है—यह बात दिमाग़ घुमा देती है। कुछ category error जैसा महसूस होता है

    • BB(748) को ZFC से independent बनाने वाली चीज़ उसका value खुद नहीं है, बल्कि यह है कि 748-state machines में से एक TM_ZFC_INC ZFC के भीतर contradiction, यानी FALSE का proof ढूंढती है और उसे मिल जाने पर ही halt करती है
      इसलिए BB(748)=N का proof या तो यह दिखाएगा कि TM_ZF_INC N steps के भीतर halt करती है, या यह कि वह कभी halt नहीं करती। अगर मानें कि ZFC consistent है, तो Gödel के प्रसिद्ध result की वजह से दोनों ही असंभव हैं
    • non-computable BB(n) है। यानी किसी भी n के लिए BB(n) value output करने वाला कोई algorithm नहीं है
      BB(748) computable है। Definition के हिसाब से यह 748 states वाली किसी Turing machine द्वारा लिखे गए 1s की संख्या है, और वही machine BB(748) को compute करती है
      संख्या खुद सचमुच कल्पना से परे बड़ी integer भर है। ZFC independence तब आती है जब हम यह prove करने की कोशिश करते हैं कि यही वह संख्या है जिसे हम खोज रहे हैं। इसके लिए ऐसी theory चाहिए जो ZFC से stronger हो और 748-state Turing machine की properties को capture कर सके
    • बल्कि ज़्यादा हैरानी की बात यह है कि हमने कभी सोचा कि ZFC axioms जैसा छोटा text, जो आराम से napkin पर आ जाए, arithmetic truth या मानव गतिविधि से मुख्य रूप से जुड़े physical reality के पहलुओं को पकड़ने के लिए “काफ़ी” होगा
      6-state Turing machine का व्यवहार कुछ lines के text से unpredictable हो सकता है—यह बिल्कुल भी चौंकाने वाली बात नहीं है
      मैंने सोचा था कि Gödel के first incompleteness theorem प्रकाशित करते ही पूरा mathematical community और axioms खोजने की दिशा में पूरी रफ़्तार से दौड़ पड़ा होगा। लेकिन लगभग एक सदी तक Gödel का काम mainstream program के बजाय foundations के एक संकरे क्षेत्र में अटकी हुई अजीब-सी बात की तरह लिया गया। Feferman, Friedman वगैरह के बारे में जानता हूं, लेकिन इस field में research mathematics के अधिकतर दूसरे topics की तुलना में बहुत कम है
    • संख्या खुद ZFC से independent नहीं है। हर integer ZFC में expressible है। ZFC से independent चीज़ BB(748) को compute करने की प्रक्रिया है
    • अलग-अलग numbers खुद non-computable नहीं होते। कोई number और ZFC के भीतर कोई proof pair ऐसा नहीं है जिससे साबित हो कि वह number BB(748) की value है
      इसलिए ऐसा program भी नहीं है जिसके बारे में ZFC prove कर सके कि वह BB(748) value output करता है। लेकिन बाकी सभी numbers की तरह BB(748) को output करने वाला program खुद मौजूद है

  • यह पता है कि BB(14) Graham's Number से बड़ा है, लेकिन इस result को देखकर लगता है कि BB(7) भी शायद Graham's Number से बड़ा होगा
    intuitively, pentation से Graham's Number तक जाने के लिए लगने वाली technique, 47,176,870 से 2 5 तक जाने के लिए लगने वाली technique से ज़्यादा simple लगती है

  • left superscript का मतलब tetration, यानी repeated exponentiation है—यह explanation देखकर पहले मुझे लगा कि typo है। tetration से पहली बार सामना हुआ

    • पहले भी देखा था, लेकिन तब Knuth's up-arrow notation इस्तेमाल हुई थी, जो आसानी से generalize हो जाती है और यह बात मुझे पसंद आई थी https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
    • repetition की इसी कड़ी में, मुझे इस बार पहली बार pentation के बारे में पता चला

  • “कल्पना कीजिए कि आपके पास 10,000,000sub10 रेत के कण हैं। तब आप उस रेत से लगभग 10,000,000sub10 देखने योग्य ब्रह्मांड भर सकते हैं” वाला हिस्सा समझ नहीं आया
    क्या सच में देखने योग्य ब्रह्मांड के आयतन को औसत रेत-कण के आयतन से भाग देने वाले मान को round करके गायब कर रहे हैं? यह तो आम तौर पर तुलना में इस्तेमाल होने वाले ब्रह्मांड के कुल द्रव्यमान से भी कहीं ज़्यादा अंकों का फर्क है

    • हाँ। उस अनुपात से भाग देने का इस notation में लगभग कोई असर नहीं पड़ता, क्योंकि यहाँ ‘पास-पास’ की संख्याएँ भी कहीं बड़े बदलाव पैदा करती हैं
      10↑↑10,000,000 / (एक ब्रह्मांड में रेत के कणों की संख्या) उदाहरण के लिए 10↑↑9,999,999 से भी जबरदस्त रूप से बड़ा है
      ऐसी संख्याओं वाली प्रणाली में (बहुत बड़ी संख्या)/(सिर्फ ब्रह्मांडीय पैमाने की संख्या) को ठीक उसी तरह लिखने के अलावा शायद ही कोई बेहतर अभिव्यक्ति हो, और बहुत बड़ी संख्या वाली notation में अंततः यह लगभग (बहुत बड़ी संख्या) पर ही round हो जाता है
    • tetration में अब हम अंकों के पैमाने से नहीं, बल्कि अंकों के पैमाने के अंकों के पैमाने से निपट रहे होते हैं
    • ऐसी तुलना का एक ज़्यादा आम उदाहरण: significant figures के हिसाब से देखें तो 1 अरब में से 10 लाख घटाने पर भी 1 अरब ही रहता है
    • सही। यह संख्या 10^100000 या कितने रेत-कण समा सकते हैं जैसी मात्राओं से इतनी ज़्यादा बड़ी है कि उतना भाग देने पर भी असल में बदलती नहीं। कम-से-कम इतनी नीचे तो नहीं आती कि 9,999,999sub10 के करीब पहुँच जाए
    • हाँ। वह तो बस एक सामान्य संख्या जितने अंकों का अंतर है। सिर्फ 10,000,000^10,000,000 ही इतना बड़ा है कि वह अंतर मायने नहीं रखता; और जब exponent को ही नौ बार और power पर चढ़ा दिया गया हो, तब तो और भी नहीं

  • Scott Aaronson का How Much Math Is Knowable? [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
    कुछ महीने पहले HN पर भी आया था: https://news.ycombinator.com/item?id=43776477

  • सिर्फ 5-state Turing machine से proofs enumerate कर सकने वाला सबसे समृद्ध logic कौन-सा होगा?

    • यह सवाल इस पर निर्भर करता है कि आप किसे enumeration मानते हैं, लेकिन इससे जुड़ा सवाल है: “वह सबसे समृद्ध logic कौन-सा है जो सभी 5-state Turing machines के halt होने या न होने को prove नहीं कर पाता?” यानी यह पूछना कि वह सबसे समृद्ध logic कौन-सा है जिसके लिए किसी 5-state Turing machine का halt होना/न होना independent है
      इस version पर मैंने थोड़ा सोचा है, लेकिन first-order logic में expertise कम होने के कारण आगे नहीं जा पाया। मेरी जानकारी में Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA गणितीय रूप से non-halting prove करने के लिए सबसे कठिन machines में से एक है https://arxiv.org/abs/2407.02426, इसलिए अगर कोई theory Skelet #17 के halt न करने को prove कर सकती है, तो संभावना है कि वह बाकी 5-state machines का भी निर्णय कर सके
    • यह पूरी तरह इस पर निर्भर करता है कि finite binary string को logical proofs की enumeration के रूप में कैसे interpret किया जाए

  • “BB(6) छठा Busy Beaver number है, यानी {0,1} alphabet वाली 6-state Turing machine जब शुरुआत में पूरी तरह 0 वाली tape पर चलती है, तो halt होने से पहले जितने steps ले सकती है, उनका maximum” वाला explanation देखकर, मुझ जैसे गैर-विशेषज्ञ को उल्टा लगा कि यह बहुत अच्छी तरह समझ में आ गया
    यह निश्चित रूप से उन लोगों के लिए hardcore blog है जो दशकों से ऐसा research कर रहे हैं। किसी खास readership के लिए बेझिझक dense और jargon-heavy लिखा गया लेख अचानक मिल जाना काफी शानदार है

    • undergraduate computer science पढ़े हुए किसी व्यक्ति के लिए, भले ही उसने Busy Beaver problem पहली बार देखा हो, यह explanation इतना है कि मोटे तौर पर समझ आ जाए कि हो क्या रहा है
      यह niche jargon जरूर है, लेकिन इसे केवल दशकों का समय लगाने वालों के लिए accessible मानना खुद को कम आँकना है
    • यह definition standard undergraduate computer science theory का हिस्सा है। हालाँकि software engineering में यह standard न हो सकता है

  • इतनी बड़ी संख्या को इंसान visualize नहीं कर सकता। संख्या को represent करने का तरीका सिर्फ गिनना ही नहीं होता
    उदाहरण के लिए रेत के एक कण की भी संभावित states अनंत मानी जा सकती हैं। real numbers अनंत हैं, इसलिए यह भी कहा जा सकता है कि रेत का एक कण BB(6) को represent कर सकता है। combinations exponentially बढ़ सकते हैं, इसलिए शायद वह तरीका representation में उपयोगी हो

    • किसी बिंदु के बाद बड़ी संख्याएँ “बड़ी मात्रा” से ज़्यादा formal system की consistency strength जैसी हो जाती हैं
      यानी बात यह है कि कोई system पकड़े जाने से पहले कितनी देर तक बिना विरोधाभास वाला होने का नाटक कर सकता है। BB(3) के जरिए consistency का नाटक करने वाला contradictory system, BB(6) के जरिए consistency का नाटक करने वाले system की तुलना में कहीं जल्दी “पकड़ा” जाएगा। यहाँ consistency का नाटक करने का मतलब है यह दावा करना कि किसी n के लिए BB(n) steps से ज़्यादा चलने वाले सभी programs halt नहीं करते
    • अगर ब्रह्मांड को सबसे नज़दीकी Planck unit तक round किया जाता है, तो रेत के एक कण की संभावित states अचानक उतनी ज़्यादा नहीं रह जातीं
      infinite precision खींच लाकर चीज़ को संभालने लायक दिखाना मेरे हिसाब से हाथ की सफाई जैसा है। scale समझाते समय integers का इस्तेमाल बेहतर है
    • यह उदाहरण उलझाने वाला है। अगर रेत-कणों की संख्या और देखने योग्य ब्रह्मांडों की संख्या बराबर है, तो इसका मतलब हर ब्रह्मांड में एक रेत-कण नहीं हुआ?

  • सोच रहा हूँ कि क्या observable universe इतना बड़ा है कि BB(6) का exact मान लिखा जा सके

    • observable universe को closed system मानें तो Bekenstein bound लागू करके देखा जा सकता है
      R ≈ 46.5 billion light-years, यानी observable universe का radius इस्तेमाल करते हैं, और E ≈ observable universe की कुल mass-energy content लेते हैं
      mass-energy में ordinary matter, dark matter और dark energy शामिल होते हैं। मौजूदा अनुमान के मुताबिक observable universe के पास लगभग 10^53 kg के mass-energy equivalent के बराबर मात्रा है
      इसे S ≤ 2πER/ℏc में डालें तो maximum information लगभग 10^120 bits के स्तर की आती है
      S ≤ 2πER/ℏc
      S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
      S ≤ 2.654135e+124
      S ≤ 10^120
      इसलिए यह असंभव है
    • यकीनन यह पर्याप्त नहीं है। universe में store की जा सकने वाली information लगभग 10^120 bits ही है। मान लें मैं 1 trillion digits जितना भी गलत हूँ, तब भी नतीजा नहीं बदलेगा
    • लेख में सिर्फ शुरुआती संख्या ही ¹⁵10 है। इसका मतलब 10^(¹⁴10) है, इसलिए digits की संख्या ¹⁴10 है। तो इसे लिखा नहीं जा सकता
    • शायद इसका मतलब यह है कि पूरी expression के सभी हिस्से एक ही समय में मौजूद हों। अगर उनका एक साथ मौजूद होना ज़रूरी न हो, तो universe की duration infinite होने पर शायद “लिख पाना” संभव हो। heat death का इस पर क्या असर होगा, मुझे नहीं पता, इसलिए बस “शायद संभव” कह रहा हूँ
      लेकिन relativistic spacetime में “एक ही समय में” कहना ठीक से defined नहीं है। sibling comments cosmic microwave background radiation से संकेतित reference frame में तो निश्चित रूप से सही हैं। फिर भी सोचता हूँ कि क्या किसी reference frame में spacetime को काटने का ऐसा तरीका हो सकता है जिससे expression “एक साथ” संभव हो जाए