प्रोग्रामर्स के लिए गुगोलॉजी (यह टाइपो नहीं है)

भौतिकी की तुलना में गणित के बारे में लिखना अधिक कठिन है (ताकि यह दिलचस्प हो)। हालांकि, मुझे आशा है कि आप कम से कम पागल सी कार्यक्रमों के उदाहरण पढ़ते हैं।


राक्षस पूरी तरह से हानिरहित चीजों से बढ़ सकते हैं। उदाहरण के लिए, सबस्ट्रिंग का खेल। हम अक्षर a और b की एक स्ट्रिंग लिखते हैं और वर्ण 1 से वर्ण 2, 2 से 4 तक, तीन से 6, n से 2n, जब तक कि मुख्य स्ट्रिंग की लंबाई पर्याप्त है, से सबस्ट्रिंग का चयन करें। हमारा काम यह सुनिश्चित करना है कि इन सबस्टीट्यूशंस में छोटे किसी भी समय में प्रवेश नहीं करते हैं। मैंने SQL पार्सर भी लिखा है:

declare @s varchar(max) = 'abbbaaaaaaab' declare @n int=1 declare @sub table (n int, sub varchar(max)) while @n*2<=len(@s) begin insert into @sub select @n,substring(@s,@n,@n+1) set @n=@n+1 end select *,(select max(sub) from @sub I where In>On and charindex(O.sub,I.sub)>0) as FoundMatch from @sub O order by 1 

यहाँ एक उदाहरण आउटपुट है:



जैसा कि आप देख सकते हैं, सबस्ट्रिंग 1 और 5 ने टेस्ट पास नहीं किया। हम अंतिम चरित्र को हटा सकते हैं, और परिणामी 11-वर्ण स्ट्रिंग 'अब्बाबासा' टेस्ट पास करेगा। यह पता चला है कि यह दो-वर्ण वर्णमाला में सबसे लंबे समय तक संभव स्ट्रिंग है जो इस स्थिति को संतुष्ट करता है।

एक वर्ण की वर्णमाला के लिए, अधिकतम स्ट्रिंग लंबाई 3 है, और फिर विशुद्ध रूप से तकनीकी कारणों से। यह पता चला है कि किसी भी संख्या के अक्षरों की वर्णमाला के लिए अधिकतम लंबाई परिमित है। तो हमारे पास है:

$$

$$f (1) = 3$$

$$

$$f (2) = 11$$

$$

$$f (3) = ???$$

तीन-अक्षर वर्णमाला में एक स्ट्रिंग को कितनी देर तक बनाया जा सकता है, इसके बारे में अपने अंतर्ज्ञान का परीक्षण करें। 100? 1000? वास्तव में, Googol से बहुत अधिक है, और GoogolPlekh से बहुत अधिक है।

$$

$$f (3)> 2 \ uparrow ^ {7198} 158836$$

और मुझे निशानेबाजों की ताकत दिखाने के लिए समय बिताना होगा।

तीर (हाइपरोपरेशन)

हम गुणा का उपयोग करते हैं ताकि कई अतिरिक्त संचालन न लिखें:

$$

$$2 * 5 = 2 + 2 + 2 + 2 + 2$$

हम घातांक का उपयोग करते हैं ताकि कई गुणा न लिखें:

$$

$$2 ^ 3 = 2 * 2 * 2$$

स्तर 0 के एक ऑपरेशन के रूप में जोड़, 1 के रूप में गुणा, 2 के रूप में घातांक को ध्यान में रखते हुए, हम ऑपरेशन "एरो" को पेश कर सकते हैं, उदाहरण के लिए,

$$

$$3 \ uparrow 3 = 3 ^ {(3 ^ 3)} = 3 ^ {27} = 7'625'597'484'987$$

ध्यान दें कि यहां कोष्ठक पहले से ही महत्वपूर्ण हैं। अगला स्तर दो तीर संचालन है:

$$

$$3 \ uparrow \ uparrow 3 = 3 \ uparrow (3 \ uparrow 3) = 3 \ uparrow 7625597484987 = 3 ^ {3 ^ {... ^ 3}}$$

तीनों के अंतिम पिरामिड की ऊंचाई 7 बिलियन है, और यह संख्या पहले से ही बहुत अधिक है, गोगोल और गोगोलिप्लेक्स की तुलना में बहुत बड़ी है। हम इस विशाल संख्या को डार्कनेस के रूप में निरूपित करते हैं (यह पुरानी रूसी भाषा में ऐसा एक अंक था) और एक और कदम उठाने की कोशिश करते हैं:

$$

$$3 \ uparrow ^ 3 3 = 3 \ uparrow \ uparrow 3 = 3 \ uparrow \ uparrow (3 \ uparrow \ uparrow 3) = 3 \ uparrow \ uparrow (डार्क) = 3 \ uparrow 3 \ uparrow 3 ... \ _ अपरोक्ष 3$$

(और इतनी बार) ... पहले से ही कल्पना है कि यह संख्या कितनी बड़ी है। कृपया ध्यान दें कि जब बहुत सारे तीर होते हैं, तो हम शीर्ष पर एक पुनरावर्तक लिखते हैं। तो आप समझ सकते हैं कि कितना अच्छा है

$$

$$f (3)> 2 \ uparrow ^ {7198} 158836$$

और अधिक

तीरों का उपयोग करते हुए, केवल बड़ी संख्या में सबसे छोटे बनाए जाते हैं, इसलिए बोलने के लिए। कार्यों की वृद्धि दर को एक निश्चित पैमाने पर मापा जाता है - तेजी से बढ़ते कार्यों के साथ तुलना करके। इस पदानुक्रम में पहला कार्य इसके अलावा, दूसरा गुणन, तीसरे से तीर, n-वें से n-2 तीर (लगभग, बिल्कुल नहीं) से मेल खाता है। लेकिन आप परिभाषित कर सकते हैं

$$

$$f_w (n) = f_n (n)$$

N = 3 के लिए इस तरह के एक फ़ंक्शन दो तीरों के साथ n = 4 के लिए एक तीर के साथ तुलनीय है, और जैसा कि पैरामीटर n बढ़ता है, यह फ़ंक्शन की वृद्धि को किसी भी स्थिर संख्या के साथ तीर से आगे बढ़ाता है।

आप आगे भी जा सकते हैं: $$$f_w, f_ {w + 1}, f_ {w + n}, f_ {w2}, f_ {w ^ 2}, f_ {w ^ w}, f_ {w ^ {w} {w}}, f_ \ epsilon$ इन कार्यों को अध्यादेशों द्वारा या रूसी साहित्य में क्रमिक संख्याओं द्वारा अनुक्रमित किया जाता है। प्रारंभिक क्रमिक संख्याओं की संरचना के साथ चित्र लेख से पहले होता है, लेकिन वे बहुत आगे बढ़ाते हैं, और आगे शुरू होते हैं

थोड़ा रहस्यवाद

ओमेगा का अंतहीन पिरामिड एक ऑर्डिनल देता है $$$\ epsilon_0$ । उस फ़ंक्शन के बारे में पढ़ें, जिसका विकास इस क्रम द्वारा मापा जाता है। यह पता चलता है कि एक फ़ंक्शन इतनी तेजी से बढ़ता है कि औपचारिक अंकगणित सिद्धांत रूप में साबित नहीं कर सकता है कि इस तरह के फ़ंक्शन को बिल्कुल भी परिभाषित किया गया है!

बेशक, आप गोडेल के प्रमेय के बारे में जानते हैं कि अप्राप्य कथन हैं। लेकिन, एक नियम के रूप में, इस तरह के एक बयान का एकमात्र उदाहरण गोडेल का खुद का निर्माण है ("मैं अप्राप्य हूं")। गुडस्टाइन का प्रमेय ऐसे कथन का एक अच्छा उदाहरण है।

इसके अलावा, यह पता चला है कि अध्यादेश किसी तरह सिद्धांतों की शक्ति को मापते हैं । औपचारिक अंकगणित की 'ताकत' है $$$\ epsilon_0$ सरलीकृत क्रिपके-प्लेटका सेट सिद्धांत में फेफरमैन-स्कुट ऑर्डिनल , आदि की ताकत है।

टिन - गणित टूर्नामेंट - सी भाषा प्रतियोगिता

बड़ी संख्या उत्पन्न करने के लिए एक प्रतियोगिता आयोजित की गई थी। नहीं, ट्यूरिंग मशीन के लिए प्रोग्रामिंग अभी भी बहुत क्रूर है, इसलिए C का उपयोग कुछ अमूर्त अनंत मशीन के लिए sizeof (int) = अनंत के साथ किया गया था। आप मॉलॉक () का उपयोग भी कर सकते हैं, और स्टैक की तरह, मेमोरी की मात्रा असीमित है। केवल कार्यक्रम की लंबाई सीमित थी - कार्यक्रम को 512 बाइट्स (रिक्त स्थान को छोड़कर) में फिट होना था, लेकिन प्रीप्रोसेसर (#define) के उपयोग की अनुमति थी।

परिणाम गणित की वेबसाइट पर प्रकाशित किए जाते हैं। उसी समय एक वास्तविक गणितज्ञ की साइट का डिज़ाइन देखें। परिणाम यहाँ हैं । यहाँ कार्यक्रम का पाठ है, जो दूसरे स्थान पर है, के बारे में संख्या दे रहा है

$$

$$f_ {w ^ w} (10 ^ {500})$$

 typedef int J; JP(J x,J y) { return x+y ? x%2 + y%2*2 + P(x/2,y/2)*4 : 0 ;} JH(J z) { return z ? z%2 + 2*H(z/4) : 0 ;} JI(J f,J e,J r){ return f ? P(P(f,e),r) : r ;} JM(J x,J e) { return x ? I(x%2, M(e,0), M(x/2, e+1)) : 0 ;} JD(J,J); JE(J f,J e,J r,J b) { return e ? E(1, D(e,b), I(b-1, D(e,b), I(f-1,e,r)), b) : I(f-1,e,r) ; } JD(J x,J b) { return x ? E( H(H(x)), H(H(x)/2), H(x/2), b) : 0 ;} JF(J x,J b) { return x ? F(D(x,b+1),b+1) : b ;} JG(J x) { return F(M(x,9), 9) ;} J f(J n,J x) { return n ? f(n-1, G(x ? f(n,x-1) : n)) : G(x) ;} J g(J x) { return f(x,x) ;} J h(J n,J x) { return n ? h(n-1, g(x ? h(n,x-1) : n)) : g(x) ;} J main(void) { return h(g(9),9) ;} 

विजेता का कार्यक्रम पाठ लंबा है, मैं सिर्फ यह दिखाना चाहता हूं कि यह कहां शुरू होता है:

 #define R { return #define PP ( #define LL ( #define TS (v, y, c, #define C ), #define X x) #define F );} 

लेकिन यहां तक ​​कि प्रतियोगिता के आयोजक ने यह मूल्यांकन करना मुश्किल पाया कि संख्या कितनी निकली ( बहुत बड़ी लिखी गई)

व्यस्त बीवर

ठीक है, छोटे नंबरों से निपटने के लिए पर्याप्त है, चलो बड़े करते हैं। कल्पना कीजिए कि सबसे बड़ी संख्या पैदा करने के लिए एक कार्यक्रम लिखने के लिए एक सार्वभौमिक प्रतियोगिता आयोजित की गई है। चूंकि कार्यक्रमों की संख्या 512 वर्णों से अधिक नहीं है, निश्चित रूप से, हमेशा एक पूर्ण विजेता होता है। आइए इसे बीबी (512) के रूप में नामित करें - व्यस्त बीवर फ़ंक्शन ।

यह स्पष्ट है कि BB (1024) >> BB (512)। लेकिन बीबी फ़ंक्शन कितनी जल्दी बढ़ता है? यह पता चला है कि यह सब कुछ है कि हम मिले से तेजी से बढ़ रहा है। BB फ़ंक्शन स्वयं ही एल्गोरिदमिक रूप से अस्वीकार्य है, इसकी गणना कंप्यूटर पर नहीं की जा सकती है। लेकिन जैसे-जैसे वैध कार्यक्रम की लंबाई बढ़ती है, हम अधिक से अधिक नए विचारों को लागू कर सकते हैं। इसलिए बीबी किसी भी एल्गोरिदमिक रूप से निर्णायक कार्य की तुलना में तेजी से बढ़ती है।

बड़ी फुंसी

ठीक है, छोटे नंबरों से निपटने के लिए पर्याप्त है, चलो बड़े करते हैं। आह, क्या मैंने पहले ही कहा था? यह बीबी (बीबी (n)) चलाने के लिए अच्छा होगा। लेकिन चूंकि बी बी कम्प्यूटेबल नहीं है, इसलिए इसके साथ तकनीकी कठिनाइयाँ होती हैं (इस तरह का एक कार्य ट्यूरिंग मशीनों में ओराकल के साथ करने योग्य है - ओरेकल डीबीएमएस के साथ ऑर्कल्स को भ्रमित करने के लिए नहीं)।

लेकिन आप इसे आसान कर सकते हैं, एक कार्यक्रम के बजाय , लंबाई n के मात्रात्मक के साथ एक सूत्र पर विचार करें। एक क्वांटिफायर सूत्र यह मायने नहीं रखता है कि कुछ गणना योग्य है या नहीं। तो आप कम से कम फ़ंक्शन BB (1,000,000,000) ले सकते हैं, और इसे अपने आप BB (BB (BB))) बार पर लागू कर सकते हैं। और यह केवल पहली बार दिमाग में आया है।

अधिकांश n वर्णों के सूत्र द्वारा निरूपित की जाने वाली सबसे बड़ी संख्या को FOOT (n) द्वारा निरूपित किया जाता है।

$$

$$बिग फोटो = फोटो ^ {10} (10 ^ {100})$$

पुनश्च

अगले लेख के लिए मैं यह समझना चाहूंगा कि किस पर ध्यान केंद्रित करना है, कृपया सर्वेक्षण में भाग लें