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

 (sligocki.com)
1 पॉइंट द्वारा GN⁺ 2024-05-25 | 1 टिप्पणियां | WhatsApp पर शेयर करें

BB(3, 4) > Ack(14)

  • 22 मई 2024
    • Pavel ने 3-स्टेट 4-सिंबल Turing Machine (TM) खोजी
    • यह मशीन एक "Ackermann-स्तर" फ़ंक्शन की गणना करती है और ठीक (2↑155)+14 non-zero symbols के साथ halt करती है
    • Knuth up-arrow notation कुछ असुविधाजनक हो जाती है, इसलिए इसे इस तरह approximate किया जा सकता है: BB(3,4)>Ack(14)
    • यहाँ Ack(14) को 14वीं Ackermann संख्या के रूप में परिभाषित किया गया है: Ack(n)=n↑nn
    • यह मशीन "wild में" खोजी गई पहली ऐसी TM है जो Ackermann-स्तर फ़ंक्शन का simulation कर सकती है

मशीन

  • स्टेट ट्रांज़िशन टेबल

    | 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3LB | 1RZ | 2RA |
| B   | 2LC | 3RB | 1LC | 2RA |
| C   | 3RB | 1LB | 3LC | 2RC |

  • अंतिम कॉन्फ़िगरेशन

    • 0∞32g153(0)+12161 Z> 0∞
    • टेप पर ठीक σ=2g153(0)+18=(2↑155)+14 non-zero symbols बचते हैं

Attribution

  • खोजकर्ता
    • यह TM Pavel Kropitz(@uni) द्वारा खोजी गई और 25 अप्रैल 2024 को Discord पर साझा की गई
    • उनका कोड TM score के लिए human-readable bound निर्दिष्ट नहीं कर सका, और इसे बस Halt(SuperPowers(13)) के रूप में दिया गया
    • उन्होंने इस परिणाम को verify करना शुरू किया, इसके लिए एक नया "inductive proof validator" इस्तेमाल किया
    • 20 मई 2024 को उन्होंने gkn(m) की सटीक परिभाषा निकाली और σ>2↑153 का bound प्राप्त किया
    • Matthew House(@LegionMammal978) ने 22 मई 2024 को gkn(0)=2↑k(n+2)2−2 का सरल closed form खोजा

विश्लेषण

  • B(k,n,m) की परिभाषा

    B(k,n,m)=0∞32m+12k A> 1n

  • प्रमाण

    0∞A>0∞→241B(16,3,0)20∞
B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
B(k,0,m)2→10∞32m+12k1Z>

  • gk(m) की परिभाषा

    g0(m)=m+1
gk+1(m)=gk2m+2(0)

दोहरी induction द्वारा प्रमाण

  • मुख्य नियम

    B(k,n,m)→B(k,0,gk−1n(m))

  • Lemma 1

    For all k≥1: 32k<B→2k+12k<B1

  • Corollary 2

    For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m

  • Theorem 3

    For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))

सटीक मान

  • Theorem

    For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)

  • Corollary

    For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)

  • निष्कर्ष

    σ=2g153(0)+18=(2↑155)+14

Permutations

  • स्टेट B से शुरू

    σB=2g63(0)+9=(2↑65)+5

  • स्टेट C से शुरू

    σC=2g03(0)+3=(2↑05)−1=9 (72 steps में halt)

  • परिवर्तित TNF

    | 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3RB | 1LC | 2LA |
| B   | 2LA | 2RB | 1LB | 3RA |
| C   | 3LA | 1RZ | 1LC | 2RA |

Not Collatz

  • दिलचस्प बात
    • यह TM आश्चर्यजनक रूप से सरल है
    • इसमें Collatz जैसी कोई rule नहीं है
    • इससे यह संभावना ख़ारिज नहीं होती कि Collatz-जैसी Ackermann-स्तर TM मौजूद हो सकती है

Inductive Proof Validator

  • प्रोजेक्ट लक्ष्य
    • एक "inductive proof" validator विकसित किया जा रहा है
    • एक standardized proof format विकसित किया जा रहा है ताकि विभिन्न inductive proofs को verify किया जा सके
    • यह अभी शुरुआती चरण में है, लेकिन कई TM के व्यवहार को prove करने में सफल रहा है

GN⁺ की राय

  • दिलचस्प पहलू

    • यह लेख Turing Machine और Ackermann फ़ंक्शन की जटिलता को समझने में बहुत मददगार है
    • सरल नियमों से जटिल computation करना आकर्षक लगता है

  • आलोचनात्मक दृष्टिकोण

    • इस मशीन की जटिलता समझने के लिए गणितीय पृष्ठभूमि की आवश्यकता है
    • व्यावहारिक उपयोग से अधिक इसका फ़ोकस सैद्धांतिक रुचि पर है

  • संबंधित तकनीक

    • inductive proof validator automated mathematical proof systems के विकास में बड़ा योगदान दे सकता है
    • इसे अन्य जटिल computation समस्याओं पर भी लागू किया जा सकता है

  • विचार योग्य बातें

    • इस तकनीक को अपनाते समय verification process की सटीकता और efficiency पर ध्यान देना चाहिए
    • जटिल गणितीय अवधारणाओं को समझने और लागू करने में समय लगता है

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

1 टिप्पणियां

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

Hacker News टिप्पणियों के संकलन का सार

  • सरल Turing machine प्रोग्राम
    यह सोचने के विपरीत कि Turing machine प्रोग्राम जटिल spaghetti code होगा, यह नया प्रोग्राम अपेक्षाकृत सरल है। इसमें तीन states (A, B, C) हैं, और state B नियंत्रण को A और C को सौंपती है, लेकिन A और C एक-दूसरे को नहीं जानते और केवल B को ही नियंत्रण सौंपते हैं। यह एक modular संरचना है; असली spaghetti code में हर state नियंत्रण को हर दूसरी state को सौंप सकती है.

  • दिलचस्प विशेषताएँ
    यह प्रोग्राम blank cell प्रिंट नहीं करता, और हर command state या color बदलती है। नया BB(3,4) रिकॉर्ड धारक लगभग 64 bits की जानकारी रखता है। BBλ(49) 49 bits में Graham's number से बहुत आगे निकल जाता है.

  • इम्प्लिमेंटेशन उदाहरण
    इसे सीधे implement करके देखने पर, state B, 0 को 2 में और 1 को 1 में बदलती है, फिर C में स्विच करती है, और state C, 3 को 2 में बदलती है, फिर A में स्विच करती है। इससे 3 की श्रेणियाँ exponentials की तरह लंबी होती जाती हैं.

  • code golf से समानता
    यह सब extreme code golf जैसा लगता है। BitGrid नाम का एक निजी hobby project प्रति cell केवल 4-bit state रखता है, और 4x4 grid अधिकतम 2^64 तक गिन सकती है। छोटे grids में edge connections परिणाम पर बड़ा असर डालते हैं.

  • Turing machine की व्याख्या संबंधी सामग्री का अनुरोध
    table को कैसे पढ़ा जाए, इस पर सामग्री की माँग की गई। यह Turing machine के विवरण जैसा लगता है.

  • Turing machine की सीमाएँ
    सीमित संख्या के symbols से वर्णित की जा सकने वाली Turing machines की संख्या सीमित है। यह आश्चर्यजनक है कि कुछ Turing machines रुकने से पहले बेहद बड़ी संख्या में steps चला सकती हैं.

  • क्या खास है, इसकी व्याख्या का अनुरोध
    इस खास instruction set के प्रभावशाली होने का कारण समझाने का अनुरोध किया गया। यह भी जिज्ञासा है कि Ackermann function स्तर का function क्या होता है और यह वास्तव में क्या compute करता है.

  • गणितीय सत्य के प्रति रुचि
    देखने में बेकार लगने वाला यह परिणाम बहुत उपयोगी LLM प्रगति की तुलना में अधिक दिलचस्प लगता है। ऐसा इसलिए क्योंकि सरल गणितीय सत्यों की ओर स्वाभाविक आकर्षण होता है.

  • BB(5) और BB(3,4) की तुलना
    यह सवाल उठा कि क्या BB(5), BB(3,4) से बड़ा है। bbchallenge.org के अनुसार BB(5) लगभग 47 million है, लेकिन कहा गया कि BB(3,4) उससे कहीं बड़ा है.

  • लेखक द्वारा संदर्भ प्रदान करना
    यह अच्छा लगा कि लेखक ने कुछ संदर्भ प्रदान किया.