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

यह छवि मैंडेलब्रॉट सेट भग्न के हिस्से को दर्शाती है। इस छवि में प्रत्येक पिक्सेल के 24-बिट रंग को संग्रहीत करने के लिए केवल 23 मिलियन बाइट्स की आवश्यकता होगी, लेकिन एक छोटा कंप्यूटर प्रोग्राम मैंडेलब्रॉट सेट की परिभाषा और छवि के कोने निर्देशांक का उपयोग करके इन 23 एमबी को पुन: उत्पन्न कर सकता है। इस प्रकार, गणना के किसी भी व्यावहारिक मॉडल में इस छवि की कोलमोगोरोव जटिलता 23 एमबी से बहुत कम है। पोर्टेबल नेटवर्क ग्राफ़िक्स का सामान्य-उद्देश्य छवि संपीड़न केवल इसे 1.6 एमबी तक कम कर देता है, जो कच्चे डेटा से छोटा है लेकिन कोलमोगोरोव जटिलता से बहुत बड़ा है।

एल्गोरिथम सूचना सिद्धांत (कंप्यूटर विज्ञान और गणित का उपक्षेत्र) में, किसी वस्तु की कोल्मोगोरोव जटिलता, जैसे पाठ का टुकड़ा, छोटे से कंप्यूटर प्रोग्राम (पूर्व निर्धारित प्रोग्रामिंग भाषा में) की लंबाई है जो ऑब्जेक्ट को आउटपुट के रूप में उत्पन्न करता है। यह वस्तु को निर्दिष्ट करने के लिए आवश्यक गणना संसाधनों का उपाय है, और इसे एल्गोरिथम जटिलता, सोलोमनॉफ-कोलमोगोरोव-चैटिन जटिलता, प्रोग्राम-आकार की जटिलता, वर्णनात्मक जटिलता, या एल्गोरिथम एंट्रोपी के रूप में भी जाना जाता है। इसका नाम एंड्री कोलमोगोरोव के नाम पर है, जिन्होंने पहली बार 1963 में इस विषय पर प्रकाशित किया था और शास्त्रीय सूचना सिद्धांत का सामान्यीकरण है।

कोल्मोगोरोव जटिलता की धारणा का उपयोग कैंटर के विकर्ण तर्क, गोडेल की अपूर्णता प्रमेय, और हॉल्टिंग समस्या | ट्यूरिंग की हॉल्टिंग समस्या के समान असम्भवता परिणामों को बताने के लिए किया जा सकता है।

विशेष रूप से, कोई भी प्रोग्राम P प्रत्येक पाठ की कोल्मोगोरोव जटिलता के लिए निचली सीमा की गणना नहीं कर सकता है, जो अनिवार्य रूप से P'की अपनी लंबाई से बड़ा मान लौटा सकता है (अनुभाग देखें) § Chaitin's incompleteness theorem); इसलिए कोई भी कार्यक्रम असीम रूप से कई पाठों के लिए सटीक कोलमोगोरोव जटिलता की गणना नहीं कर सकता है।

विशेष रूप से, कोई भी प्रोग्राम P प्रत्येक पाठ की कोल्मोगोरोव जटिलता के लिए निचली सीमा की गणना नहीं कर सकता है, जो अनिवार्य रूप से P'की अपनी लंबाई से बड़ा मान लौटा सकता है (अनुभाग देखें) § Chaitin's incompleteness theorem); इसलिए कोई भी कार्यक्रम

परिभाषा

32 लोअरकेस अक्षरों और अंकों के निम्नलिखित दो स्ट्रिंग (कंप्यूटर विज्ञान) पर विचार करें:

abababababababababababababababab , और

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

पहली स्ट्रिंग में संक्षिप्त अंग्रेजी-भाषा विवरण है, अर्थात् 16 बार लिखें, जिसमें 17 अक्षर होते हैं। दूसरे वाले का कोई स्पष्ट सरल विवरण नहीं है (समान वर्ण सेट का उपयोग करके) स्ट्रिंग को लिखने के अलावा, यानी, 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7 लिखें जिसमें 38 वर्ण हैं। इसलिए पहली स्ट्रिंग लिखने की संक्रिया को दूसरी स्ट्रिंग लिखने की तुलना में कम जटिल कहा जा सकता है।

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

कोलमोगोरोव जटिलता को किसी भी गणितीय वस्तु के लिए परिभाषित किया जा सकता है, लेकिन सरलता के लिए इस लेख का दायरा स्ट्रिंग्स तक ही सीमित है। हमें पहले स्ट्रिंग्स के लिए विवरण भाषा निर्दिष्ट करनी होगी। ऐसी विवरण भाषा किसी भी कंप्यूटर प्रोग्रामिंग भाषा पर आधारित हो सकती है, जैसे कि लिस्प प्रोग्रामिंग भाषा, पास्कल (प्रोग्रामिंग भाषा), या जावा (प्रोग्रामिंग भाषा)। यदि P प्रोग्राम है जो स्ट्रिंग x को आउटपुट करता है, तो P x का विवरण है। विवरण की लंबाई वर्ण स्ट्रिंग के रूप में केवल P की लंबाई है, जिसे किसी वर्ण में बिट्स की संख्या से गुणा किया जाता है (उदाहरण के लिए, ASCII के लिए 7)।

हम, वैकल्पिक रूप से, ट्यूरिंग मशीन के लिए एन्कोडिंग चुन सकते हैं, जहां एन्कोडिंग फ़ंक्शन है जो प्रत्येक ट्यूरिंग मशीन M को बिटस्ट्रिंग <M> से जोड़ता है। यदि एम ट्यूरिंग मशीन है, जो इनपुट w पर, स्ट्रिंग x को आउटपुट करती है, तो श्रृंखलाबद्ध स्ट्रिंग <M> w x का विवरण है। सैद्धांतिक विश्लेषण के लिए, यह दृष्टिकोण विस्तृत औपचारिक प्रमाणों के निर्माण के लिए अधिक अनुकूल है और आमतौर पर शोध साहित्य में इसे पसंद किया जाता है। इस लेख में, अनौपचारिक दृष्टिकोण पर चर्चा की है।

किसी भी स्ट्रिंग s का कम से कम विवरण होता है। उदाहरण के लिए, उपरोक्त दूसरी स्ट्रिंग छद्म कोड द्वारा आउटपुट है:

समारोह GenerateString2 ()
    वापसी 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

जबकि पहली स्ट्रिंग (बहुत कम) छद्म कोड द्वारा आउटपुट होती है:

समारोह GenerateString1 ()
    एबी × 16 लौटें

यदि किसी स्ट्रिंग s का वर्णन d(s) न्यूनतम लंबाई का है (यानी, सबसे कम बिट्स का उपयोग करके), तो इसे s का न्यूनतम विवरण कहा जाता है, और d(s) की लंबाई (यानी न्यूनतम विवरण में बिट्स की संख्या) s की कोलमोगोरोव जटिलता है, जिसे K(s) लिखा गया है। . प्रतीकात्मक रूप से,

क(s) = |d(s)|.

सबसे छोटे विवरण की लंबाई विवरण भाषा के चुनाव पर निर्भर करेगी; लेकिन बदलती भाषाओं का प्रभाव सीमित है (परिणाम को 'इनवेरियन प्रमेय कहा जाता है)।

आक्रमण प्रमेय

अनौपचारिक उपचार

कुछ विवरण भाषाएं हैं जो इष्टतम हैं, निम्नलिखित अर्थों में: किसी विवरण भाषा में किसी वस्तु का कोई विवरण दिया गया है, कहा गया विवरण निरंतर ओवरहेड के साथ इष्टतम विवरण भाषा में उपयोग किया जा सकता है। स्थिरांक केवल शामिल भाषाओं पर निर्भर करता है, न कि वस्तु के विवरण पर, न ही वस्तु का वर्णन किया जा रहा है।

यहाँ इष्टतम वर्णन भाषा का उदाहरण दिया गया है। विवरण के दो भाग होंगे:

• पहला भाग अन्य विवरण भाषा का वर्णन करता है।
• दूसरा भाग उस भाषा में वस्तु का वर्णन है।

अधिक तकनीकी शब्दों में, विवरण का पहला भाग कंप्यूटर प्रोग्राम है (विशेष रूप से: ऑब्जेक्ट की भाषा के लिए कंपाइलर, विवरण भाषा में लिखा गया है), दूसरे भाग के साथ उस कंप्यूटर प्रोग्राम का इनपुट होता है जो ऑब्जेक्ट को आउटपुट के रूप में उत्पन्न करता है।

निश्चरता प्रमेय इस प्रकार है: किसी भी विवरण भाषा 'एल' को देखते हुए, इष्टतम विवरण भाषा कम से कम 'एल' के रूप में कुशल है, कुछ निरंतर ओवरहेड के साथ।

प्रमाण: L में किसी भी विवरण D को पहले L को कंप्यूटर प्रोग्राम P (भाग 1) के रूप में वर्णित करके और फिर उपयोग करके इष्टतम भाषा में विवरण में परिवर्तित किया जा सकता है। उस कार्यक्रम के इनपुट के रूप में मूल विवरण डी (भाग 2)। इस नए विवरण 'डी की कुल लंबाई (लगभग) है:

|डी | = |पी| + |डी|

पी की लंबाई स्थिरांक है जो डी पर निर्भर नहीं करता है। तो, वर्णित वस्तु के बावजूद, अधिकतर निरंतर ओवरहेड होता है। इसलिए, इष्टतम भाषा इस योज्य स्थिरांक तक सार्वभौमिक है।

एक अधिक औपचारिक उपचार

प्रमेय: यदि के₁ और के₂ ट्यूरिंग पूर्ण विवरण भाषाओं एल के सापेक्ष जटिलता कार्य हैं₁ और मैं₂, तब एक स्थिर c - होता है जो केवल L भाषाओं पर निर्भर करता है₁ और मैं₂ चुना हुआ - ऐसा कि

∀एस। -सी ≤ के₁(स) - के₂(एस) ≤ सी।

'सबूत': समरूपता से, यह साबित करने के लिए पर्याप्त है कि कुछ निरंतर सी ऐसा है कि सभी तारों के लिए

क₁(एस) ≤ के₂(एस) + सी।

अब, मान लीजिए कि L भाषा में प्रोग्राम है₁ जो एल के लिए दुभाषिया (कंप्यूटिंग) के रूप में कार्य करता है₂:

समारोह व्याख्या भाषा (स्ट्रिंग पी)

जहां p'L में एक प्रोग्राम है₂. दुभाषिया निम्नलिखित संपत्ति द्वारा विशेषता है:

दौड़ना InterpretLanguage इनपुट पी पर चलने वाले पी का नतीजा देता है।

इस प्रकार, यदि 'पी' एल में एक कार्यक्रम है₂ जो s का एक न्यूनतम विवरण है, फिर InterpretLanguage(पी) स्ट्रिंग एस लौटाता है। स के इस वर्णन की लंबाई का योग है

1. कार्यक्रम की लंबाई InterpretLanguage, जिसे हम अचर c मान सकते हैं।
2. 'P' की लंबाई जो परिभाषा के अनुसार K है₂(एस)।

यह वांछित ऊपरी सीमा को सिद्ध करता है।

इतिहास और संदर्भ

एल्गोरिथम सूचना सिद्धांत कंप्यूटर विज्ञान का क्षेत्र है जो कोलमोगोरोव जटिलता और स्ट्रिंग्स (या अन्य डेटा संरचनाओं) पर अन्य जटिलता उपायों का अध्ययन करता है।

कोल्मोगोरोव कॉम्प्लेक्सिटी की अवधारणा और सिद्धांत पहली बार रे सोलोमनॉफ द्वारा खोजे गए महत्वपूर्ण प्रमेय पर आधारित है, जिन्होंने इसे 1960 में प्रकाशित किया था, जो इसे आगमनात्मक अनुमान के सामान्य सिद्धांत पर प्रारंभिक रिपोर्ट में वर्णित करता है। एल्गोरिथम संभाव्यता के अपने आविष्कार के हिस्से के रूप में। उन्होंने अपने 1964 के प्रकाशनों, ए फॉर्मल थ्योरी ऑफ़ इंडक्टिव इन्वेंशन, भाग 1 और भाग 2 में सूचना और नियंत्रण में अधिक संपूर्ण विवरण दिया। एंड्री कोलमोगोरोव ने बाद में इस प्रमेय को प्रॉब्लम इंफॉर्मेशन में कई बार खोजा। हस्तांतरण 1965 में। ग्रेगरी चैतिन जे. एसीएम में भी इस प्रमेय को प्रस्तुत करते हैं - चैटिन का पेपर अक्टूबर 1966 में प्रस्तुत किया गया था और दिसंबर 1968 में संशोधित किया गया था, और सोलोमनॉफ और कोलमोगोरोव दोनों के पेपर का हवाला दिया। प्रमेय कहता है कि, एल्गोरिदम के बीच जो उनके विवरण (कोड) से तारों को डीकोड करते हैं, वहां इष्टतम मौजूद होता है। यह एल्गोरिथम, सभी स्ट्रिंग्स के लिए, कोड को किसी भी अन्य एल्गोरिथम द्वारा अनुमत योगात्मक स्थिरांक तक कम करने की अनुमति देता है जो एल्गोरिदम पर निर्भर करता है, लेकिन स्वयं स्ट्रिंग्स पर नहीं। सोलोमनॉफ़ ने इस एल्गोरिथम का उपयोग किया और कोड की लंबाई यह स्ट्रिंग की सार्वभौमिक संभावना को परिभाषित करने की अनुमति देती है, जिस पर स्ट्रिंग के बाद के अंकों का आगमनात्मक निष्कर्ष आधारित हो सकता है। कोल्मोगोरोव ने इस प्रमेय का उपयोग जटिलता, यादृच्छिकता और सूचना सहित तार के कई कार्यों को परिभाषित करने के लिए किया।

जब कोलमोगोरोव को सोलोमनॉफ के काम के बारे में पता चला, तो उन्होंने सोलोमनॉफ की प्राथमिकता को स्वीकार किया। कई सालों तक, पश्चिमी दुनिया की तुलना में सोवियत संघ में सुलैमानॉफ का काम बेहतर जाना जाता था। हालांकि, वैज्ञानिक समुदाय में आम सहमति कोलमोगोरोव के साथ इस प्रकार की जटिलता को जोड़ने के लिए थी, जो अनुक्रम की यादृच्छिकता से संबंधित थी, जबकि एल्गोरिथम संभाव्यता सोलोमनॉफ से जुड़ी हुई थी, जिसने सार्वभौमिक पूर्व संभाव्यता वितरण के अपने आविष्कार का उपयोग करके भविष्यवाणी पर ध्यान केंद्रित किया था। . वर्णनात्मक जटिलता और संभाव्यता को शामिल करने वाले व्यापक क्षेत्र को अक्सर कोलमोगोरोव जटिलता कहा जाता है। कंप्यूटर वैज्ञानिक मिंग एल आई इसे मैथ्यू प्रभाव (समाजशास्त्र) का उदाहरण मानते हैं: ...जिसके पास है, उसे अधिक दिया जाएगा... कोलमोगोरोव जटिलता या एल्गोरिथम जानकारी के कई अन्य रूप हैं। सबसे व्यापक रूप से इस्तेमाल किया जाने वाला स्व-सीमांकन कार्यक्रमों पर आधारित है, और मुख्य रूप से लियोनिद लेविन (1974) के कारण है।

ब्लम स्वयंसिद्ध (ब्लम 1967) पर आधारित कोलमोगोरोव जटिलता के लिए स्वयंसिद्ध दृष्टिकोण मार्क बर्गिन द्वारा एंड्री कोलमोगोरोव द्वारा प्रकाशन के लिए प्रस्तुत किए गए पेपर में पेश किया गया था।

मूल परिणाम

निम्नलिखित चर्चा में, K(s) को स्ट्रिंग s की जटिलता होने दें।

यह देखना कठिन नहीं है कि किसी स्ट्रिंग का न्यूनतम विवरण स्वयं स्ट्रिंग—प्रोग्राम से बहुत बड़ा नहीं हो सकता है GenerateString2 इसके ऊपर आउटपुट s निश्चित राशि है जो s से बड़ी है।

'प्रमेय': स्थिर सी ऐसा है कि

∀एस। के(एस) ≤ |एस| + सी।

कोलमोगोरोव जटिलता की अगणनीयता

==== K ==== की गणना करने के लिए कार्यक्रम में भोला प्रयास

पहली नज़र में ऐसा प्रोग्राम लिखना तुच्छ लग सकता है जो किसी भी s के लिए K(s) की गणना कर सकता है, जैसे कि निम्नलिखित:

'फ़ंक्शन' कोलमोगोरोव कॉम्प्लेक्सिटी ('स्ट्रिंग' एस)
    'के लिए' मैं = 1 'से' अनंत:
        'प्रत्येक के लिए' स्ट्रिंग पी 'का' लंबाई बिल्कुल मैं
            'अगर' isValidProgram (पी) 'और' मूल्यांकन (पी) == एस
                'वापसी' मैं

यह कार्यक्रम सभी संभावित कार्यक्रमों के माध्यम से पुनरावृति करता है (सभी संभावित तारों के माध्यम से पुनरावृति करके और केवल उन पर विचार करता है जो वैध कार्यक्रम हैं), सबसे कम से शुरू होता है। प्रत्येक प्रोग्राम को उस प्रोग्राम द्वारा उत्पादित परिणाम को खोजने के लिए निष्पादित किया जाता है, इसकी तुलना इनपुट एस से की जाती है। यदि परिणाम मेल खाता है तो कार्यक्रम की लंबाई वापस आ जाती है।

हालांकि यह काम नहीं करेगा क्योंकि पी परीक्षण किए गए कुछ कार्यक्रम समाप्त नहीं होंगे, उदा। अगर उनमें अनंत लूप हैं। हॉल्टिंग समस्या की गैर-संगणनीयता के कारण इन सभी कार्यक्रमों को निष्पादित करने से पहले किसी तरह से परीक्षण करके इन सभी कार्यक्रमों से बचने का कोई तरीका नहीं है।

क्या अधिक है, कोई भी प्रोग्राम फ़ंक्शन K की गणना नहीं कर सकता है, चाहे वह कितना भी परिष्कृत क्यों न हो। यह निम्नलिखित में सिद्ध होता है।

==== K==== की अगणनीयता का औपचारिक प्रमाण

'प्रमेय': मनमाने ढंग से बड़ी कोलमोगोरोव जटिलता के तार मौजूद हैं। औपचारिक रूप से: प्रत्येक प्राकृतिक संख्या n के लिए, K(s) ≥ n के साथ स्ट्रिंग s है। सबूत: अन्यथा असीमित रूप से कई संभावित परिमित तारों को अंततः कई लोगों द्वारा उत्पन्न किया जा सकता है एन बिट्स के नीचे जटिलता वाले कार्यक्रम।

'प्रमेय': K संगणनीय फलन नहीं है। दूसरे शब्दों में, ऐसा कोई प्रोग्राम नहीं है जो किसी भी स्ट्रिंग को इनपुट के रूप में लेता है और आउटपुट के रूप में पूर्णांक K(s) उत्पन्न करता है।

विरोधाभास द्वारा निम्नलिखित प्रमाण | विरोधाभास द्वारा 'प्रमाण' कार्यक्रमों को निरूपित करने के लिए साधारण पास्कल (प्रोग्रामिंग भाषा) जैसी भाषा का उपयोग करता है; प्रमाण सरलता के लिए इसके विवरण (अर्थात दुभाषिया (कंप्यूटिंग)) की लंबाई मान लें 1400000 बिट्स। विरोधाभास के लिए मान लें कि कार्यक्रम है

समारोह KolmogorovComplexity (स्ट्रिंग एस)

जो इनपुट के रूप में स्ट्रिंग s लेता है और K(s) लौटाता है। सभी कार्यक्रम परिमित लंबाई के होते हैं, इसलिए सरलता के प्रमाण के लिए, इसे मान लें 7000000000 बिट्स। अब, लंबाई के निम्नलिखित प्रोग्राम पर विचार करें 1288 बिट्स:

समारोह GenerateComplexString ()
    मैं = 1 अनंत के लिए:
        लंबाई के प्रत्येक स्ट्रिंग एस के लिए बिल्कुल i
            अगर कोलमोगोरोव कॉम्प्लेक्सिटी (एस) ≥ 8000000000
                वापसी एस

का उपयोग करते हुए KolmogorovComplexity उपनेमका के रूप में, कार्यक्रम हर स्ट्रिंग की कोशिश करता है, सबसे कम से शुरू होता है, जब तक कि यह कम से कम कोलमोगोरोव जटिलता के साथ स्ट्रिंग नहीं लौटाता 8000000000 बिट्स, यानी स्ट्रिंग जिसे किसी भी प्रोग्राम से छोटा नहीं बनाया जा सकता है 8000000000 बिट्स। हालाँकि, उपरोक्त प्रोग्राम की कुल लंबाई जो s का उत्पादन करती है, केवल है 7001401288 बिट्स, जो विरोधाभास है। (यदि का कोड KolmogorovComplexity छोटा है, विरोधाभास बना रहता है। यदि यह लंबा है, तो इसमें प्रयुक्त स्थिरांक GenerateComplexString हमेशा उचित रूप से बदला जा सकता है।) उपरोक्त प्रमाण बेरी विरोधाभास के समान विरोधाभास का उपयोग करता है:_{1 2}उब> सबसे छोटा ₃सकारात्मक ₄पूर्णांक ₅वह ₆नही सकता ₇होना ₈परिभाषित ₉में ₁₀से कम ₁₁बजाय ₁₂बीस ₁₃अंग्रेज़ी ₁₄शब्द । हॉल्टिंग समस्या H की गैर-कम्प्यूटेबिलिटी से घटाकर K की गैर-कम्प्यूटेबिलिटी दिखाना भी संभव है, क्योंकि K और H ट्यूरिंग डिग्री # ट्यूरिंग समतुल्य | ट्यूरिंग-समतुल्य हैं। प्रोग्रामिंग भाषा समुदाय में एक उपप्रमेय है, जिसे हास्यपूर्वक पूर्ण रोजगार प्रमेय कहा जाता है, जिसमें कहा गया है कि कोई सही आकार-अनुकूलन संकलक नहीं है।

कोलमोगोरोव जटिलता के लिए चेन नियम

Main article: Chain rule for Kolmogorov complexity

चेन नियम कोल्मोगोरोव जटिलता के लिए कहा गया है कि

के (एक्स, वाई) ≤ के (एक्स) + के (वाई | एक्स) + ओ (लॉग (के (एक्स, वाई)))।

इसमें कहा गया है कि एक्स और वाई को पुन: उत्पन्न करने वाला सबसे छोटा प्रोग्राम बिग-ओ नोटेशन है, एक्स को पुन: उत्पन्न करने के लिए लघुगणकीय शब्द से बड़ा है और वाई दिए गए एक्स को पुन: पेश करने के लिए कार्यक्रम है। इस कथन का उपयोग करके, कोई पारस्परिक जानकारी # पूर्ण पारस्परिक जानकारी को परिभाषित कर सकता है।

संपीड़न

K(s) के लिए ऊपरी सीमा की गणना करना सरल है – बस किसी विधि से स्ट्रिंग s को आधार - सामग्री संकोचन करें, चुनी हुई भाषा में संबंधित डीकंप्रेसर को लागू करें, डीकंप्रेसर को असंपीड्य स्ट्रिंग से जोड़ें, और परिणामी स्ट्रिंग की लंबाई को मापें – ठोस रूप से , दिए गए भाषा में स्वयं-निकालने वाले संग्रह का आकार।

स्ट्रिंग एस संख्या सी द्वारा संपीड़ित होता है यदि इसका विवरण होता है जिसकी लंबाई |s| से अधिक नहीं होती है - सी बिट्स। यह K(s) ≤ |s| कहने के बराबर है - सी। अन्यथा, s, c द्वारा असम्पीडित है। 1 से असम्पीडित स्ट्रिंग को केवल असम्पीडित कहा जाता है - कबूतर सिद्धांत द्वारा, जो लागू होता है क्योंकि प्रत्येक संपीड़ित स्ट्रिंग केवल असम्पीडित स्ट्रिंग के लिए मैप करती है, असंपीड़ित स्ट्रिंग मौजूद होनी चाहिए, क्योंकि 2 हैंⁿ बिट स्ट्रिंग्स की लंबाई n, लेकिन केवल 2ⁿ − 1 छोटी स्ट्रिंग्स, यानी n से कम लंबाई वाली स्ट्रिंग्स, (यानी लंबाई 0, 1, ..., n − 1 के साथ)। इसी कारण से, अधिकांश तार इस अर्थ में जटिल होते हैं कि उन्हें महत्वपूर्ण रूप से संकुचित नहीं किया जा सकता है - उनका K(s) |s|, बिट्स में s की लंबाई से बहुत छोटा नहीं है। इसे सटीक बनाने के लिए, n का मान ठीक करें। वहाँ 2 है^{n </super> बिट स्ट्रिंग्स की लंबाई n। बिट स्ट्रिंग्स के स्थान पर समान वितरण (असतत) संभाव्यता वितरण बिल्कुल बराबर वजन 2 प्रदान करता है−n लंबाई n की प्रत्येक स्ट्रिंग के लिए।}

'प्रमेय': लंबाई n के बिटस्ट्रिंग्स के स्थान पर समान संभावना वितरण के साथ, संभावना है कि स्ट्रिंग सी द्वारा असम्पीडित है कम से कम 1 − 2 है^−c+1 + 2^{-एन</सुप>.}

प्रमेय को सिद्ध करने के लिए, ध्यान दें कि n − c से अधिक लंबाई के विवरण की संख्या ज्यामितीय श्रृंखला द्वारा दी गई है:

1 + 2 + 2² + ... + 2^{n − c} = 2^n−c+1 − 1.

कम से कम रहता है

2^एन − 2^n−c+1 + 1

लंबाई n की बिटस्ट्रिंग्स जो c द्वारा असम्पीडित हैं। संभावना निर्धारित करने के लिए, 2 से विभाजित करें^एन.

चैटिन की अपूर्णता प्रमेय

कोलमोगोरोव जटिलता K(s), और दो कम्प्यूटेशनल लोअर बाउंड फ़ंक्शंस prog1(s), prog2(s). क्षैतिज अक्ष (लघुगणकीय पैमाना) सभी स्ट्रिंग (कंप्यूटर विज्ञान) की गणना करता है, लंबाई द्वारा क्रमबद्ध; ऊर्ध्वाधर अक्ष (रैखिक पैमाना) अंश ्स में कोलमोगोरोव जटिलता को मापता है। अधिकांश तार असम्पीडित होते हैं, अर्थात उनकी कोलमोगोरोव जटिलता स्थिर मात्रा से उनकी लंबाई से अधिक हो जाती है। तस्वीर में 9 सिकुड़ने योग्य तार दिखाए गए हैं, जो लगभग लंबवत ढलान के रूप में दिखाई दे रहे हैं। चैतिन की अपूर्णता प्रमेय (1974) के कारण, कोलमोगोरोव जटिलता की निचली सीमा की गणना करने वाले किसी भी प्रोग्राम का आउटपुट कुछ निश्चित सीमा से अधिक नहीं हो सकता है, जो इनपुट स्ट्रिंग s से स्वतंत्र है।

उपरोक्त प्रमेय द्वारा (§ Compression), अधिकांश तार इस अर्थ में जटिल हैं कि उन्हें किसी भी तरह से संकुचित तरीके से वर्णित नहीं किया जा सकता है। हालांकि, यह पता चला है कि तथ्य यह है कि विशिष्ट स्ट्रिंग जटिल है औपचारिक रूप से सिद्ध नहीं किया जा सकता है, यदि स्ट्रिंग की जटिलता निश्चित सीमा से ऊपर है। सटीक औपचारिकता इस प्रकार है। सबसे पहले, प्राकृतिक संख्याओं के लिए विशेष स्वयंसिद्ध प्रणाली S को ठीक करें। स्वयंसिद्ध प्रणाली को पर्याप्त शक्तिशाली होना चाहिए ताकि, स्ट्रिंग्स की जटिलता के बारे में कुछ अभिकथन A के लिए, सूत्र F को संबद्ध किया जा सके_A एस में। इस एसोसिएशन में निम्नलिखित संपत्ति होनी चाहिए:

अगर एफ_A S के स्वयंसिद्धों से सिद्ध है, तो संबंधित कथन A सत्य होना चाहिए। गोडेल नंबरिंग के आधार पर यह औपचारिकता हासिल की जा सकती है।

प्रमेय: स्थिर 'एल' मौजूद है (जो केवल एस पर निर्भर करता है और विवरण भाषा की पसंद पर निर्भर करता है) जैसे कि स्ट्रिंग एस मौजूद नहीं है जिसके लिए बयान

क(s) ≥ एल       (एस में औपचारिक रूप से)

S के भीतर सिद्ध किया जा सकता है।

प्रमाण विचार: इस परिणाम का प्रमाण बेरी के विरोधाभास में प्रयुक्त स्व-संदर्भात्मक निर्माण पर आधारित है। हम सबसे पहले प्रोग्राम प्राप्त करते हैं जो एस के भीतर सबूतों की गणना करता है और हम प्रक्रिया 'पी' निर्दिष्ट करते हैं जो इनपुट के रूप में पूर्णांक 'एल' लेता है और स्ट्रिंग्स 'एक्स' को प्रिंट करता है जो एस के सबूत के भीतर हैं। कथन के(x) ≥ एल। फिर इस प्रक्रिया P की लंबाई से अधिक L को सेट करके, हमारे पास K(x) में बताए अनुसार x को प्रिंट करने के लिए प्रोग्राम की आवश्यक लंबाई है। ) ≥ L कम से कम L होने के कारण राशि L से कम है क्योंकि स्ट्रिंग x को P प्रक्रिया द्वारा प्रिंट किया गया था। यह विरोधाभास है। इसलिए प्रूफ सिस्टम S के लिए K(x) ≥ L को L के लिए मनमाने ढंग से बड़ा साबित करना संभव नहीं है, विशेष रूप से, L से बड़ा प्रक्रिया की लंबाई पी, (जो परिमित है)।

सबूत:

हम किसी प्रक्रिया द्वारा S में सभी औपचारिक प्रमाणों की प्रभावी गणना पा सकते हैं

फ़ंक्शन NthProof (int n)

जो इनपुट n के रूप में लेता है और कुछ प्रमाण को आउटपुट करता है। यह फ़ंक्शन सभी प्रमाणों की गणना करता है। इनमें से कुछ सूत्रों के लिए प्रमाण हैं जिनकी हम यहाँ परवाह नहीं करते हैं, क्योंकि S की भाषा में हर संभव प्रमाण कुछ 'n' के लिए निर्मित होता है। इनमें से कुछ K(s) ≥ n रूप के जटिल सूत्र हैं जहां s और n S की भाषा में स्थिरांक हैं। प्रक्रिया

फ़ंक्शन NthProofProvesComplexityFormula(int n)

जो यह निर्धारित करता है कि क्या n वाँ प्रमाण वास्तव में जटिलता सूत्र K('s) ≥ L साबित करता है। तार एस, और पूर्णांक एल बदले में, प्रक्रिया द्वारा संगणनीय हैं:

समारोह StringNthProof (इंट एन)

फ़ंक्शन कॉम्प्लेक्सिटीलोअरबाउंडNthProof(int n)

निम्नलिखित प्रक्रिया पर विचार करें:

फ़ंक्शन GenerateProvablyComplexString (int n)
    मैं = 1 अनंत के लिए:
        अगर NthProofProvesComplexityFormula(i) और ComplexityLowerBoundNthProof(i) ≥ n
            वापसी StringNthProof(i)

एन दिए जाने पर, यह प्रक्रिया तब तक हर प्रमाण को आजमाती है जब तक कि उसे सूत्र के(एस) ≥ एल के फॉर्मूले की औपचारिक प्रणाली एस में एक स्ट्रिंग और प्रमाण नहीं मिल जाता। 'एल ≥ एन; यदि ऐसा कोई प्रमाण मौजूद नहीं है, तो यह हमेशा के लिए लूप हो जाता है।

अंत में, इन सभी प्रक्रिया परिभाषाओं और मुख्य कॉल से युक्त कार्यक्रम पर विचार करें:

GenerateProvablyComplexString(n0)

जहां निरंतर n₀ बाद में तय किया जाएगा। समग्र कार्यक्रम की लंबाई यू + लॉग के रूप में व्यक्त की जा सकती है₂(एन₀), जहां यू कुछ स्थिर और लॉग है₂(एन₀) पूर्णांक मान n की लंबाई का प्रतिनिधित्व करता है₀उचित धारणा के तहत कि यह बाइनरी अंकों में एन्कोड किया गया है। हम एन चुनेंगे₀ कार्यक्रम की लंबाई से अधिक होना, अर्थात, ऐसा है कि n₀ > यू + लॉग₂(एन₀). यह एन के लिए स्पष्ट रूप से सच है₀ पर्याप्त रूप से बड़ा है, क्योंकि बायां हाथ n में रैखिक रूप से बढ़ता है₀ जबकि दाहिने हाथ की ओर n में लघुगणकीय रूप से बढ़ता है₀ निश्चित स्थिर यू तक।

तब L≥n के साथ K(s)≥L के रूप का कोई प्रमाण नहीं₀ एस में प्राप्त किया जा सकता है, जैसा कि अप्रत्यक्ष तर्क द्वारा देखा जा सकता है: अगर ComplexityLowerBoundNthProof(i) मान ≥n लौटा सकता है₀, फिर लूप अंदर GenerateProvablyComplexString अंततः समाप्त हो जाएगा, और वह प्रक्रिया स्ट्रिंग एस वापस कर देगी

	K(s)
≥	n0		by construction of GenerateProvablyComplexString
>	U+log2(n0)		by the choice of n0
≥	K(s)		since s was described by the program with that length

यह विरोधाभास है, Q.E.D.

परिणामस्वरूप, उपरोक्त प्रोग्राम, n के चुने हुए मान के साथ₀, हमेशा के लिए लूप होना चाहिए।

चैटिन स्थिरांक के गुणों को सिद्ध करने के लिए इसी तरह के विचारों का उपयोग किया जाता है।

न्यूनतम संदेश लंबाई

Main article: Minimum message length

सांख्यिकीय और आगमनात्मक अनुमान और मशीन सीखने का न्यूनतम संदेश लंबाई सिद्धांत क्रिस वालेस (कंप्यूटर वैज्ञानिक) | सी.एस. द्वारा विकसित किया गया था। वालेस और डी.एम. 1968 में बोल्टन। एमएमएल बायेसियन प्रायिकता है (यानी यह पूर्व मान्यताओं को शामिल करता है) और सूचना-सैद्धांतिक। इसमें सांख्यिकीय आक्रमण के वांछनीय गुण हैं (अर्थात पुन: पैरामीट्रिजेशन के साथ अनुमान बदल जाता है, जैसे कि ध्रुवीय निर्देशांक से कार्टेशियन निर्देशांक तक), सांख्यिकीय स्थिरता (अर्थात बहुत कठिन समस्याओं के लिए भी, MML किसी भी अंतर्निहित मॉडल में परिवर्तित हो जाएगा) और दक्षता ( यानी एमएमएल मॉडल जितनी जल्दी हो सके किसी भी वास्तविक अंतर्निहित मॉडल में परिवर्तित हो जाएगा)। सीएस वालेस और डी.एल. डोवे (1999) ने एमएमएल और एल्गोरिथम सूचना सिद्धांत (या कोलमोगोरोव जटिलता) के बीच औपचारिक संबंध दिखाया।

कोलमोगोरोव यादृच्छिकता

See also: Algorithmic randomness

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

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

एन्ट्रॉपी से संबंध

गतिशील प्रणालियों के लिए, एंट्रॉपी दर और ट्रैजेक्टोरियों की एल्गोरिथम जटिलता ब्रुडनो के प्रमेय द्वारा संबंधित हैं, कि समानता $K(x;T)=h(T)$ लगभग सभी के लिए रखता है $x$. इसे दिखाया जा सकता है कि मार्कोव सूचना स्रोतों के उत्पादन के लिए, कोलमोगोरोव जटिलता सूचना स्रोत के एंट्रॉपी (सूचना सिद्धांत) से संबंधित है। अधिक सटीक रूप से, मार्कोव सूचना स्रोत के आउटपुट की कोलमोगोरोव जटिलता, आउटपुट की लंबाई से सामान्यीकृत, लगभग निश्चित रूप से (आउटपुट की लंबाई अनंत तक जाती है) स्रोत के एंट्रॉपी (सूचना सिद्धांत) में परिवर्तित हो जाती है।

सशर्त संस्करण

दो तारों की सशर्त कोलमोगोरोव जटिलता $K(x|y)$ मोटे तौर पर बोल रहा हूँ, प्रक्रिया के सहायक इनपुट के रूप में दिए गए x के कोलमोगोरोव जटिलता के रूप में परिभाषित किया गया है। लंबाई-सशर्त जटिलता भी है $K(x|L(x))$, जो ज्ञात/इनपुट के रूप में x की लंबाई दी गई x की जटिलता है।

यह भी देखें

• बेरी विरोधाभास
• कोड गोल्फ
• आधार - सामग्री संकोचन
• वर्णनात्मक जटिलता सिद्धांत
• व्याकरण प्रेरण
• आगमनात्मक अनुमान
• कोलमोगोरोव संरचना समारोह
• लेवेनशेटिन दूरी
• सोलोमनॉफ का आगमनात्मक अनुमान का सिद्धांत
• नमूना एन्ट्रापी

अग्रिम पठन

• Blum, M. (1967). "On the size of machines". Information and Control. 11 (3): 257. doi:10.1016/S0019-9958(67)90546-3.
• Brudno, A. (1983). "Entropy and the complexity of the trajectories of a dynamical system". Transactions of the Moscow Mathematical Society. 2: 127–151.
• Cover, Thomas M.; Thomas, Joy A. (2006). Elements of information theory (2nd ed.). Wiley-Interscience. ISBN 0-471-24195-4.
• Lajos, Rónyai; Gábor, Ivanyos; Réka, Szabó (1999). Algoritmusok. TypoTeX. ISBN 963-279-014-6.
• Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. ISBN 978-0387339986.
• Yu, Manin (1977). A Course in Mathematical Logic. Springer-Verlag. ISBN 978-0-7204-2844-5.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS. ISBN 0-534-95097-3.

बाहरी संबंध

• The Legacy of Andrei Nikolaevich Kolmogorov
• Chaitin's online publications
• Solomonoff's IDSIA page
• Generalizations of algorithmic information by J. Schmidhuber
• "Review of Li Vitányi 1997".
• Tromp, John. "John's Lambda Calculus and Combinatory Logic Playground". Tromp's lambda calculus computer model offers a concrete definition of K()]
• Universal AI based on Kolmogorov Complexity ISBN 3-540-22139-5 by M. Hutter: ISBN 3-540-22139-5
• David Dowe's Minimum Message Length (MML) and Occam's razor pages.
• Grunwald, P.; Pitt, M.A. (2005). Myung, I. J. (ed.). Advances in Minimum Description Length: Theory and Applications. MIT Press. ISBN 0-262-07262-9.