सोवियत लाइसेंस प्लेट और कोलमोगोरोव जटिलता

भौतिक विज्ञानी लेव लैंडौ ने सोवियत संख्या [ 1 ] के साथ एक मानसिक खेल खेला। गोलियाँ दो संख्याओं, एक डैश, दो और संख्याओं और कुछ अक्षरों के रूप में थीं।

खेल के नियम

उनका खेल गणितीय ऑपरेटरों को डैश के दोनों ओर संख्याओं पर लागू करना था ताकि डैश को एक समान चिह्न से बदला जा सके। उदाहरण के लिए, यदि आप नंबर प्लेट 44-74 लेते हैं, तो इसका एक समाधान होगा

4! + 4 = 7 * 4

कृपया ध्यान दें कि हम जैसे ऑपरेटर डाल सकते हैं ! , + और * , लेकिन संख्याओं को जोड़े बिना।

क्या हर संभव लाइसेंस प्लेट के लिए एक समाधान है? यह निर्भर करता है कि आप किन ऑपरेटरों को उपयोग करने की अनुमति देते हैं।

आप दोनों पक्षों को आंशिक भाग ऑपरेशन {x} लागू करके खेल को तुच्छ बना सकते हैं, क्योंकि पूर्णांक का अंश आंशिक है। आप इस आधार पर आंशिक अंश संचालक को प्रतिबंधित कर सकते हैं कि यह स्पष्ट रूप से हाई स्कूल का गणितीय संचालन नहीं है, या इसे केवल इसलिए निषिद्ध कर देता है क्योंकि यह खेल को निर्बाध बनाता है।

अनुवाद EDISON सॉफ़्टवेयर द्वारा समर्थित था, जो आशाजनक स्टार्टअप्स में निवेश करता है , और विभिन्न क्लाउड सेवाओं को भी विकसित करता है ।

एक बंद समाधान

यह पता चला है कि एक सार्वभौमिक समाधान है, जो अवलोकन के साथ शुरू होता है

) (N + 1) = sec arctan 1 n।

यदि एक पक्ष दूसरे से बड़ा है, तो ऊपर दिया गया सूत्र तत्काल समाधान देता है। उदाहरण के लिए, लाइसेंस प्लेट नंबर 89-88 के लिए एक समाधान होगा

√89 = सेकंड आर्कटिक√88।

यदि अंतर अधिक है, तो सूत्र को बार-बार लागू किया जा सकता है। उदाहरण के लिए, हम पाने के लिए दो बार फार्मूला लागू कर सकते हैं

) (N + 2) = sec arctan n (n + 1) = sec arctan sec arctan√ n

और इसलिए 35-37 के लिए एक संभावित समाधान है

sec arctan sec आर्कटिक √35 = ar37।

कोलमोगोरोव जटिलता

यह देखते हुए कि एक समाधान हमेशा संभव होता है, हम सबसे सरल समाधान ढूंढकर खेल को और अधिक रोचक बना सकते हैं। हमें इसका सहज ज्ञान है कि इसका क्या अर्थ है। हमारे उदाहरण के साथ 44-74, पहला समाधान

4! + 4 = 7 * 4

सार्वभौमिक समाधान की तुलना में सरल

sec arctan sec arctan ... ct44 = ar74

जिसे 30 बार धर्मनिरपेक्ष और अभिजात वर्ग के उपयोग की आवश्यकता होगी।

किसी वस्तु की कोलमोगोरोव जटिलता किसी वस्तु को बनाने के लिए सबसे छोटे कंप्यूटर प्रोग्राम की लंबाई है। हम प्रत्येक पक्ष पर संख्याओं के लिए लागू किए गए कार्यों के कोलमोगोरोव जटिलता की गणना कर सकते हैं कि उपाय कितना जटिल है।

यह पता लगाने के लिए, हमें यह इंगित करने की आवश्यकता है कि हमारे पास कौन सी प्रोग्रामिंग भाषा है, और यह उतना सरल नहीं है जितना लगता है। अगर हम गणितीय संकेतन को एक प्रोग्रामिंग भाषा मानते हैं, तो क्या हम गिनना चाहते हैं! एक वर्ण की तरह और 6 वर्णों की तरह अर्कतन? यह सही नहीं लगता। अगर हमने "अर्टन" को "atn" के रूप में लिखा है, तो हम एक और समाधान बनाए बिना कम वर्णों का उपयोग करेंगे।

पायथन कोड जटिलता

चीजों को अधिक उद्देश्य के लिए, हम एक प्रोग्रामिंग भाषा के रूप में वर्तमान गणितीय संकेतन के बजाय वास्तविक कंप्यूटर कार्यक्रमों की लंबाई पर विचार कर सकते हैं। मान लीजिए कि हमने पायथन को चुना। फिर यहां कुछ फ़ंक्शन हैं जो हमारे दो लाइसेंस प्लेट समाधान 44-74 की गणना करते हैं।

from math import sqrt, cos, atan def f(): sec = lambda x: 1/cos(x) y = sqrt(44) for _ in range(30): y = sec(atan(y)) return y def g(): return sqrt(77) 

हम प्रत्येक में वर्णों की संख्या की गणना करके अपने कार्यों की जटिलता को माप सकते हैं। लेकिन अभी भी मुश्किलें हैं।

आयात के बारे में क्या? इसकी लंबाई को च के साथ जोड़ना चाहिए क्योंकि यह सभी आयातित कथनों का उपयोग करता है, लेकिन जी ने एक छोटे कथन का उपयोग किया है जो केवल आयातित sqrt का उपयोग करता है। अधिक मौलिक रूप से, क्या हम एक पुस्तकालय आयात करने के लिए भी मूर्ख बना रहे हैं?

इसके अलावा, दो उपर्युक्त फ़ंक्शन सीमित सटीकता के कारण बिल्कुल समान परिणाम नहीं देते हैं। हम कल्पना कर सकते हैं कि हमारे आयातित कार्य असीम रूप से सटीक हैं, लेकिन तब हम वास्तव में पायथन का उपयोग नहीं करते हैं, बल्कि पायथन का एक आदर्श संस्करण है।

पाश के बारे में क्या? इसने नए नंबर, 3 और 0 को पेश किया, और इसलिए यह लैंडौ गेम के नियमों का उल्लंघन करता है। तो क्या हमें जटिलता की गणना करने से पहले अनियंत्रित होना चाहिए?

सोचा प्रयोग

कोलमोगोरोव की जटिलता एक बहुत ही उपयोगी अवधारणा है, लेकिन यह आपके व्यवहार से अधिक मानसिक प्रयोग है। हम कुछ की गणना करने के लिए सबसे छोटे कार्यक्रम की कल्पना कर सकते हैं, लेकिन हम शायद ही कभी जानते हैं कि हम वास्तव में इस तरह के कार्यक्रम को ढूंढते हैं। व्यवहार में हम जो कुछ भी जान सकते हैं वह ऊपरी सीमा है।

सैद्धांतिक रूप से, आप किसी दिए गए लम्बाई के सभी ट्यूरिंग मशीनों या किसी दिए गए लम्बाई के सभी पायथन कार्यक्रमों को सूचीबद्ध कर सकते हैं और सबसे छोटा पा सकते हैं जो इस कार्य को करता है, लेकिन सूची बढ़ती लंबाई के साथ तेजी से बढ़ती है।

हालांकि, विशिष्ट कार्यक्रमों की अवधि की गणना करना संभव है, अगर हम ऊपर उल्लिखित कुछ कठिनाइयों से निपट रहे हैं। हम लैंडौ को दो के लिए एक खेल बना सकते हैं, जिसे देखकर निश्चित समय में सरल समाधान की पेशकश की जा सकती है।

वापस लन्दौ

यदि हम अपने ऑपरेटरों के सेट में साइन और डिग्री की अनुमति देते हैं, तो बी.एस. गोरोबेट्स एक सार्वभौमिक समाधान है। N ≥ 6, n के लिए! 360 के कई, और इसी तरह

sin (n!) ° = 0।

और यदि n 6 से कम है, तो इसका दो अंकों का प्रतिनिधित्व शून्य से शुरू होता है, इसलिए हम शून्य प्राप्त करने के लिए संख्याओं को गुणा कर सकते हैं।

यदि हम पारलौकिक कार्यों को प्रतिबंधित करते हैं, तो हम गोरोबेट्स ट्रिक को रोकते हैं और हमारे पास ऐसे कार्य हैं जिनकी लंबाई हम प्रोग्रामिंग भाषा में माप सकते हैं।