BB(3, 4) > Ack(14) का परिणाम

 (sligocki.com)
1 पॉइंट द्वारा GN⁺ 2024-05-25 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • नया 3-state 4-symbol Busy Beaver चैंपियन TM खोजा गया है, और गणना के अनुसार यह रुकने पर ((2 \uparrow^{15} 5) + 14) nonzero symbols छोड़ता है
  • यह संख्या Knuth up-arrow notation में भी बेहद बड़ी है, इसलिए इसे (BB(3,4) > Ack(14)) की निचली सीमा के रूप में संक्षेपित किया गया है, जहाँ 14वाँ Ackermann number (Ack(n)=n \uparrow^n n) से परिभाषित है
  • TM का मुख्य व्यवहार लगभग (B(k,n,m) \to B(k,0,g_{k-1}^n(m))) के रूप में संक्षेपित किया जा सकता है, लेकिन इसे दिखाने के लिए double induction की आवश्यकता होती है
  • Matthew House के closed-form evaluation (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2) की बदौलत अंतिम स्कोर (\sigma=(2 \uparrow^{15}5)+14) को सटीक रूप से लिखा जा सका
  • यह TM Collatz-जैसी remainder branching के बिना भी Ackermann-level functions को simulate करता है, और विकसित हो रहे Inductive Proof Validator के verification case के रूप में भी इस्तेमाल होता है

नए Busy Beaver चैंपियन का पैमाना

  • Pavel Kropitz ने नया 3-state 4-symbol Busy Beaver चैंपियन खोजा
  • यह TM “Ackermann-level” function की गणना कर सकता है, और रुकने पर tape पर निम्न संख्या में nonzero symbols छोड़ता है
    • ((2 \uparrow^{15} 5) + 14)
  • यह Knuth up-arrow notation में भी बहुत बड़ा मान है, इसलिए निचली सीमा को इस प्रकार संक्षेपित किया गया है
    • (BB(3,4) > Ack(14))
  • यहाँ (Ack(14)), (Ack(n)=n \uparrow^n n) से परिभाषित 14वाँ Ackermann number है
  • ज्ञात दायरे में, वास्तविक खोज के दौरान मिले TM में यह पहला उदाहरण है जो Ackermann-level function को simulate कर सकता है

TM की परिभाषा और अंतिम configuration

  • TM transition string इस प्रकार है
    • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
  • transition table state A, B, C और symbol 0, 1, 2, 3 के लिए परिभाषित है
    • A: 1RB, 3LB, 1RZ, 2RA
    • B: 2LC, 3RB, 1LC, 2RA
    • C: 3RB, 1LB, 3LC, 2RC
  • अंतिम configuration इस प्रकार है
    • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
  • इस configuration में स्कोर (\sigma) को सटीक रूप से गणना किया जाता है
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

खोज और verification प्रक्रिया

  • Pavel Kropitz ने यह TM 25 अप्रैल 2024 को Discord पर साझा किया
  • उस समय code मानव-पठनीय score lower bound निर्दिष्ट नहीं कर पा रहा था, और परिणाम को Halt(SuperPowers(13)) के रूप में दिखाया गया
    • इसका अर्थ है कि proof में 13 स्तर के induction rules की आवश्यकता थी
  • बाद में नए Inductive Proof Validator का उपयोग करके verification शुरू हुआ
  • 20 मई 2024 को verification पूरा होने पर (g_k^n(m)) की सटीक परिभाषा निकाली गई, और इसके माध्यम से (\sigma > 2 \uparrow^{15} 3) की lower bound प्राप्त हुई
  • Matthew House ने 22 मई 2024 को निम्न सरल closed-form evaluation खोजा
    • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
  • इस evaluation की मदद से (\sigma) का सटीक मान व्यक्त किया जा सका

व्यवहार विश्लेषण और double induction proof

  • निम्न configuration परिभाषित की जाती है
    • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
  • शुरुआती configuration 241 steps के बाद निम्न state तक पहुँचती है
    • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
  • मुख्य नियम इस प्रकार है
    • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), जहाँ (k \ge 1)
  • (g_k) निम्न recursive equations से परिभाषित है
    • (g_0(m)=m+1)
    • (g_{k+1}(m)=g_k^{2m+2}(0))
  • पूरा व्यवहार लगभग एक ही नियम में समाहित हो जाने जितना सरल है, लेकिन इसी नियम को double induction से सिद्ध करना पड़ता है
  • lemma और corollary B state द्वारा 3 और 2^k blocks को process करके 1 बनाने की प्रक्रिया को संभालते हैं
    • (3;;2^k;;\text{<B} \xrightarrow{2k+1} 2^k;;\text{<B};;1)
    • (3^m;;2^k;;\text{<B} \xrightarrow{(2k+1)m} 2^k;;\text{<B};;1^m)
  • Theorem 3 दिखाता है कि सभी (k \ge 1, n \ge 0, m \ge 0) के लिए मुख्य नियम सही है
    • (k=1) का base case, (n) पर induction से संभाला जाता है
    • induction step में (k) पर hypothesis और (n) पर induction hypothesis दोनों का उपयोग होता है

सटीक मान की गणना

  • (g_k) के लिए Knuth up-arrow और arithmetic का उपयोग करने वाला अपेक्षाकृत सरल closed-form evaluation है
  • सभी (k \ge 0, m \ge 0) के लिए निम्न सत्य है
    • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
    • जहाँ (a \uparrow^0 b = ab) के रूप में परिभाषित है
  • इस परिणाम को (k) पर induction द्वारा सिद्ध किया जाता है
    • base case (k=0) पर (g_1(m)=2m+2) मिलता है
    • induction step में ((2 \uparrow^k)^n) की repeated application का उपयोग होता है
  • यह closed form इस संयोग पर निर्भर करता है कि (2 \uparrow^k 2 = 4) सभी (k) के लिए सत्य है
    • यदि parameter थोड़ा बदलकर ((2 \uparrow^k)^{2m+2}5) जैसा रूप बन जाता, तो closed-form expression पाना कठिन होता
  • corollary के रूप में सभी (k \ge 0, n \ge 0) के लिए निम्न सत्य है
    • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
  • अंतिम स्कोर सीधे इस प्रकार निकाला जाता है
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

शुरुआती state बदलने पर permutation परिणाम

  • शुरुआती state को B या C में बदलने पर इससे छोटे संबंधित परिणाम मिलते हैं
    • (0^\infty ;; \text{B>} ;; 0^\infty \xrightarrow{86} B(7,3,0);;2;;0^\infty)
    • (0^\infty ;; \text{C>} ;; 0^\infty \xrightarrow{20} B(1,3,0);;2;;0^\infty)
  • B शुरुआती state होने पर स्कोर इस प्रकार है
    • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
  • C शुरुआती state होने पर यह 72 steps में रुकता है, और स्कोर इस प्रकार है
    • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
  • B से शुरू होने वाला पहला permutation भी एक और शीर्ष-स्तरीय BB(3,4) TM है
  • इसे TNF में बदलने पर transition string इस प्रकार बनती है
    • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

Collatz-जैसे नियमों के बिना सरलता

  • इस TM की दिलचस्प बातों में से एक यह है कि यह अपेक्षा से अधिक सरल है
  • इसमें मान के remainder के अनुसार अलग व्यवहार करने वाले Collatz-like rules नहीं हैं
  • Collatz-like TM का प्रभुत्व समाप्त हो गया है या नहीं, यह कहना अभी बहुत जल्दबाज़ी होगी
  • अभी भी Ackermann-level Collatz-like TM मौजूद हो सकते हैं, लेकिन selection bias के कारण वे तुरंत दिखाई न दें — ऐसा अनुमान है
  • यह संभव है कि यह TM पहला Ackermann-level TM इसलिए मिला क्योंकि यह इतना सरल था कि Ackermann-level function के ऊपर modular arithmetic लागू किए बिना भी halting proof संभव हो सका

Inductive Proof Validator

  • यह TM विकसित हो रहे Inductive Proof Validator के लिए एक उपयुक्त test case था
  • इस project का लक्ष्य “inductive proofs” के लिए standardized certificate format बनाना है
  • यहाँ “inductive proof” शब्द का उपयोग forward reasoning और rule-based analysis के व्यापक अर्थ में किया गया है
  • विचार यह है कि जिसके पास भी “inductive decider” हो, वह संबंधित rules को इस format में लिख सके, और validator उस proof की जाँच कर सके
  • system अभी बहुत शुरुआती और असुविधाजनक है, और वास्तविक उपयोग के लिए तैयार नहीं है, लेकिन थोड़े manual work के बाद इस TM सहित कई TM के व्यवहार के proof में इसका उपयोग किया गया

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

1 टिप्पणियां

 
GN⁺ 2024-05-25
Hacker News की राय

  • यह सोचना आसान है कि बहुत लंबे समय तक चलने वाला Turing machine program गहराई से जटिल या spaghetti code जैसा होगा, लेकिन यह नया champion लगभग इसका counterexample है
    इसमें केवल तीन states A, B, C हैं, और B control को A और C को सौंपता है, लेकिन A और C एक-दूसरे को “जानते” नहीं हैं और सिर्फ B पर लौटते हैं
    अगर यह सचमुच spaghetti code होता, तो हर state बाकी सभी states में जा सकता था, लेकिन यह एक तरह की modular structure है
    साथ ही यह कभी blank cell print नहीं करता, और हर instruction state या color में से कम-से-कम एक को बदलता है, इसलिए B1 -> 1LB जैसी सिर्फ position हिलाने वाली “lazy instruction” भी नहीं है

    • bbchallenge project के अंदर भी इस पर बहस है कि मौजूदा लंबे समय तक चलने वाले champions की properties सचमुच उस size पर सबसे लंबे चलने वाली machines की properties हैं, या फिर यह streetlight effect है जिसमें केवल वही properties दिख रही हैं जिन्हें automatic search और proof से आसानी से संभाला जा सकता है
      जब तक पूरे search space को deterministic या heuristic तरीके से exclude नहीं किया जाता, यह पता नहीं चल सकता
      BB(5, 2) से बड़े सभी sizes में ऐसी chaotic और pseudo-random machines शामिल हैं जिनके हमेशा चलते रहने की उम्मीद है, लेकिन number theory में बड़े progress के बिना इसे prove नहीं किया जा सकता
      हालांकि माना जाता है कि लंबे समय तक चलने वाली machine पूरी तरह chaotic नहीं हो सकती
      क्योंकि अगर वह tape पर random numbers की तरह symbols उड़ेलती है, तो जल्द ही वह halting configuration, cyclic configuration, या simplified pattern तक पहुंच जाएगी
      फिर भी ऐसी machine संभव है जो किसी higher level पर chaotic चीज़ को simulate करे, और हर high-level step के बीच बेहिसाब समय खर्च करके फिर रुक जाए
    • n-state s-symbol Turing machine अधिकतम n अलग-अलग states में ही transition कर सकती है
      इसलिए अगर s=4 या s=2 है, तो केवल बहुत छोटी Turing machines ही spaghetti code जैसी बन सकती हैं

  • नया BB(3,4) record holder यह है
    0 1 2 3
    A 1RB 3LB 1RZ 2RA
    B 2LC 3RB 1LC 2RA
    C 3RB 1LB 3LC 2RC
    row s, column t में (t', d, s') का अर्थ है: state s में tape head के नीचे symbol t होने पर transition
    symbol t को t' से overwrite करता है, direction d के अनुसार left/right जाता है, फिर state को s' में बदलता है, और अगर s' == Z है तो halt करता है
    यह 3*4*log2(4*2*log2(4+1)), यानी लगभग 64 bits information है
    दूसरी ओर, केवल 49 bits का BBλ(49) Graham number से भी बहुत आगे निकल जाता है https://oeis.org/A333479

    • अलग-अलग Turing machines की संख्या गिनना सरल नहीं है
      ऊपर की calculation सबसे broad तरीका है, जिसमें हर cell को कोई भी (symbol, direction, state) combination रखने वाला माना गया है, इसलिए यह arbitrary Turing machine को describe करने के लिए needed bits को काफी overestimate करती है
      BB(3, 4) के मामले में Tree Normal Form, यानी Brady algorithm(https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html) का उपयोग करने पर अलग-अलग Turing machines केवल करीब 600 billion निकलती हैं, इसलिए यह 40 bits से कम आता है
    • इस program में 1RZ का 1R किसी randomly चुनी गई value जैसा दिखता है
      क्योंकि वहां halt हो जाता है, इसलिए tape पर क्या बचता है या head कहां move करता है, फर्क नहीं पड़ता
      असल में 1 लिखना भी महत्वपूर्ण नहीं है, लेकिन अगर 0 लिखा जाता तो शायद optimal नहीं होता
      उस position पर पहले से 2 लिखा हुआ था और वह 1 में बदलता है, लेकिन tape पर symbols की संख्या के आधार पर 2 भी वैसे ही गिना जाता
    • मुझे ठीक से समझ नहीं आता कि log2(4+1) term कहां से आता है
      3*4*log2(4*2*log2(4+1)) calculate करने पर लगभग 51 आता है, और एक non-expert के नजरिए से 3*4*log2(4*2*4) = 60 लगना चाहिए था
      सोच रहा हूं कि कहीं यह 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64 तो नहीं है

  • behavior जानने की curiosity में मैंने इसे यहां implement किया: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
    थोड़ी देर run करने पर दिखता है कि क्या हो रहा है
    state B 0 को 2 में, 1 को 1 में बदलकर C में transition करता है, और state C 3 को 2 में बदलकर A में transition करता है
    इसलिए 2 -> 1 को ठीक करने के लिए सभी 3 से एक बार गुजरना पड़ता है, जिससे 3 की लगातार range बार-बार exponentially बढ़ती जाती है

    • हमेशा exponentially बढ़ती रहने वाली Turing machine बनाना काफी आसान है
      सच में समझना मुश्किल हिस्सा यह है कि अकल्पनीय रूप से बहुत सारे steps के बाद यह आखिर रुकती क्यों है

  • यह सब extreme code golf जैसा सुनाई देता है
    दूसरी दिशा में BitGrid नाम की चीज़ देखी जा सकती है
    BitGrid में हर cell की state केवल 4 bits की होती है, इसलिए 4x4 cell grid किसी भी हालत में 2^64 से ज्यादा count नहीं कर सकता
    असल में यह कितना count कर सकता है, यह खोजना दिलचस्प होगा, और छोटे grids में edge connections result पर हावी होंगे
    https://esolangs.org/wiki/Bitgrid
    https://github.com/mikewarot/Bitgrid

  • यह तालिका शायद Turing machine का विवरण लगती है; इसे कैसे पढ़ना है, इसके लिए कोई अच्छी सामग्री मिले तो अच्छा होगा

    • state A, B, C goto target के बराबर हैं, और color 0, 1, 2, 3 execution के दौरान का data है
      हर state में current color पढ़कर, उस color के हिसाब से “कौन-सा color output करना है, left/right जाना है, किस state में जाना है” वाली command चलती है
      C में बदलें तो इसे switch (SCAN) और WRITE, RIGHT/LEFT, goto से सीधे व्यक्त किया जा सकता है
      जानना चाहता हूँ कि इस logic को और structured style में दोबारा लिखा जा सकता है या कोई और optimization की गुंजाइश है
    • हर row एक state है, और हर column वह symbol है जो अभी tape से पढ़ा गया है
      उदाहरण के लिए पहली row का पहला column मतलब “symbol 0 पढ़ा गया और current state A है”
      table का cell की जाने वाली action दिखाता है; 1RB का मतलब है “tape के symbol को 1 में बदलो, एक cell right जाओ, फिर state B में switch करो”
      state Z halt state के बराबर है
    • Python में tape index को left/right ले जाने वाले L(), R() functions रखकर, (state, current symbol) को (symbol to write, move function, next state) पर map करने वाली table बनाएं और state != 'Z' तक loop करते रहें
    • आसान explanation https://bbchallenge.org/story#turing-machines पर है
      1RZ को halt transition समझ सकते हैं, क्योंकि state Z के लिए कोई rule नहीं है
      Wikipedia पर भी ज्यादा detailed Turing machine state table examples हैं https://en.wikipedia.org/wiki/Turing_machine#Formal_definition, और इस specific Turing machine का execution trace https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC पर देखा जा सकता है
    • current record holders को इकट्ठा करके Wolfram Language में चलाने का example दिखाने वाला एक छोटा repository बनाया था: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/
      लगता है अब इसे भी update करना पड़ेगा

  • basic computer science के किसी बड़े result का citation Discord link हो, यह भी कोई बात हुई

    • समझ नहीं आता इसमें दिक्कत क्यों है
      यह विचार कि scientific result publish करने का इकलौता valid तरीका तथाकथित peer-reviewed journal ही है, 200 साल पहले की विरासत है, जब scientific community Dunbar number के भीतर समा जाने लायक छोटी थी
      आज भी इसे पकड़े रहने की वजह यह है कि कुछ ताकतवर academics और publishers को इससे फायदा होता है, न कि science की progress के लिहाज से इसका कोई वास्तविक advantage है
      बल्कि modern reproducibility crisis के लिए इसका काफी बड़ा जिम्मेदार होना भी संभव है
      मैं scientific method का मजबूत समर्थक हूँ, लेकिन traditional peer review की expiry date बहुत पहले निकल चुकी है
      https://en.wikipedia.org/wiki/Dunbar%27s_number
    • फिर भी यह public Discord server है, और invite link https://bbchallenge.org के top right में मिल जाता है
      मुझे ये citation से ज्यादा source attribution जैसे लगते हैं
      result को support करने वाली main arguments blog post में ज्यादा rigorous form में reproduce की गई हैं, इसलिए वे independently stand करती हैं; Discord link सिर्फ interested लोगों के लिए historical context देता है
    • ऐसे chat में participate करके देखें तो यह break room के blackboard पर idea सोचकर उसे साथ में develop करने जैसा है, फर्क बस इतना है कि interaction cite किया जा सकता है
      अगर सही समय पर literature से support किया जा सके, तो यह positive change है
    • शिकायत समझ में आती है, लेकिन हाल के mathematics के कई impressive advances तेज collaboration और iteration से आए हैं
      उदाहरण के लिए Zhang के prime gaps upper bound को improve करने वाला project ऐसा ही था, और इस मायने में दूसरे communication tools Discord की जगह आसानी से नहीं ले सकते
      जहाँ actual लोग इकट्ठा हैं, वहीं जाना पड़ता है
    • बड़े Busy Beaver numbers ढूँढ़ना, strictly speaking, foundational काम से ज्यादा recreational mathematics के करीब है
      अगर यह सच में foundational होता, तो इसे blog पर डालने के बजाय journal paper के रूप में peer review कराया गया होता

  • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC जैसे बहुत ज्यादा बड़े न होने वाले symbol count से describe की जा सकने वाली Turing machines की संख्या सीमित है
    लेकिन यह तथ्य सचमुच हैरान करता है कि उनमें से कुछ halt होने से पहले इतने absurdly ज्यादा steps चला सकती हैं

    • ऐसी 3-state 4-symbol Turing machines 2^60 हैं
      output, यानी normal form Graham number से बड़ा होने वाला 49-bit lambda term, इससे भी ज्यादा surprising होना चाहिए

  • ईमानदारी से कहूँ तो मैं इन्हें 100% समझता नहीं हूँ और शायद ये results लगभग किसी काम के भी नहीं हैं, फिर भी अविश्वसनीय रूप से useful LLM advances से ज्यादा ऐसी चीजें मुझे आकर्षित करती हैं
    शायद इसलिए कि “complex” engineering results की तुलना में simple mathematical truths की तरफ natural attraction ज्यादा होता है

  • BB(5) > BB(3,4) नहीं है क्या?
    https://bbchallenge.org पर लिखा है कि वे BB(5) के लगभग 47 million होने के अनुमान को prove या disprove करने की कोशिश कर रहे हैं, जबकि BB(3,4) उससे कहीं बड़ा लगता है

    • सही, BB(3, 4) >>> BB(5, 2) लगता है
      BB(5) = BB(5, 2) है, और BB(3, 4) की table में 12 transitions (3*4) हैं जबकि BB(5, 2) में सिर्फ 10, इसलिए यह बहुत surprising नहीं है
      लेकिन लगता है BB(3, 4) >> BB(6, 2) भी हो सकता है
      दोनों में transition count समान है, इसलिए ऐसी छोटी Turing machines में symbols की ज्यादा संख्या काफी valuable लगती है