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

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

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

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

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

परिभाषा

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

abababababababababababababababab , और

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

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

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

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

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

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

function GenerateString2()
    return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

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

function GenerateString1()
    return "ab" × 16

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

k(s) = |d(s)|.

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

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

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

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

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

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

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

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

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

इस नए विवरण 'd की कुल लंबाई (लगभग) है |

|d | = |p| + |d|

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

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

प्रमेय यदि K₁ और K₂ ट्यूरिंग पूर्ण विवरण भाषाओं L₁ और L₂ के सापेक्ष जटिलता कार्य हैं तो एक स्थिर c है | जो केवल L₁ और L₂ चुनी गई भाषाओं पर निर्भर करता है | जैसे कि

∀s. −c ≤ K₁(s) − K₂(s) ≤ c

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

K₁(s) ≤ K₂(s) + c

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

function InterpretLanguage(string p)

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

दौड़ना व्याख्या भाषा इनपुट p पर चलने वाले p का परिणाम स्वरुप देता है।

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

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

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

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

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

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

एंड्री कोलमोगोरोव ने बाद में इस प्रमेय को प्रॉब्लम इंफॉर्मेशन में कई बार खोजा। हस्तांतरण 1965 में ग्रेगरी चैतिन जे. एसीएम में भी इस प्रमेय को प्रस्तुत करते हैं | चैटिन का पेपर अक्टूबर 1966 में प्रस्तुत किया गया था और दिसंबर 1968 में संशोधित किया गया था, और सोलोमनॉफ और कोलमोगोरोव दोनों के पेपर का हवाला दिया।

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

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

कोलमोगोरोव जटिलता या एल्गोरिथम जानकारी के कई अन्य रूप हैं। सबसे व्यापक रूप से उपयोग किया जाने वाला स्व-सीमांकन प्रोग्राम पर आधारित है, और मुख्य रूप से लियोनिद लेविन (1974) के कारण है।

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

मूल परिणाम

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

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

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

∀s. K(s) ≤ |s| + c

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

K की गणना करने के लिए प्रोग्राम में सरल प्रयास होता है |

पहली नज़र में ऐसा प्रोग्राम लिखना व्यर्थ लग सकता है | जो किसी भी s के लिए K(s) की गणना कर सकता है | जैसे कि निम्नलिखित:

function KolmogorovComplexity(string s)
    for i = 1 to infinity:
        for each string p of length exactly i
            if isValidProgram(p) and evaluate(p) == s
                return i

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

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

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

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

प्रमाण: अन्यथा असीमित रूप से कई संभावित परिमित तारों को अंततः कई लोगों द्वारा उत्पन्न किया जा सकता है | एन बिट्स के नीचे जटिलता वाले प्रोग्राम है।

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

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

विरोधाभास के लिए मान लें कि प्रोग्राम है |

function KolmogorovComplexity(string s)

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

function GenerateComplexString()
    for i = 1 to infinity:
        for each string s of length exactly i
            if KolmogorovComplexity(s) ≥ 8000000000
                return s

KolmogorovComplexity उपनेमका के रूप में,उपयोग करते हुए प्रोग्राम हर स्ट्रिंग की प्रयास करता है | सबसे कम से प्रारंभ होता है | जब तक कि यह कम से कम 8000000000 बिट्स, कोलमोगोरोव जटिलता के साथ स्ट्रिंग नहीं लौटाता अर्थात स्ट्रिंग जिसे 8000000000 बिट्स किसी भी प्रोग्राम से छोटा नहीं बनाया जा सकता है। चूंकि, उपरोक्त प्रोग्राम की कुल लंबाई जो s का उत्पादन करती है, केवल है 7001401288 बिट्स, जो विरोधाभास है। (यदि का कोड KolmogorovComplexity छोटा है, विरोधाभास बना रहता है। यदि यह लंबा है, तो इसमें प्रयुक्त स्थिरांक GenerateComplexString सदैव उचित रूप से बदला जा सकता है।)

उपरोक्त प्रमाण बेरी विरोधाभास के समान विरोधाभास का उपयोग करता है | _{1 2}उब> सबसे छोटा ₃सकारात्मक ₄पूर्णांक ₅वह ₆नही सकता ₇होना ₈परिभाषित ₉में ₁₀से कम ₁₁अतिरिक्त ₁₂बीस ₁₃अंग्रेज़ी ₁₄शब्द । हॉल्टिंग समस्या H की गैर-कम्प्यूटेबिलिटी से घटाकर K की गैर-कम्प्यूटेबिलिटी दिखाना भी संभव है | क्योंकि K और H ट्यूरिंग डिग्री ट्यूरिंग समतुल्य होते है |

प्रोग्रामिंग भाषा समुदाय में एक उपप्रमेय है | जिसे हास्यपूर्वक पूर्ण रोजगार प्रमेय कहा जाता है | जिसमें कहा गया है कि कोई सही आकार-अनुकूलन संकलक नहीं है।

कोलमोगोरोव जटिलता के लिए श्रृंखला नियम

Main article: कोल्मोगोरोव जटिलता के लिए श्रृंखला नियम

श्रृंखला नियम कोल्मोगोरोव जटिलता के लिए कहा गया है कि

K(X,Y) ≤ K(X) + K(Y|X) + O(log(K(X,Y))).

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

संपीड़न

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

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

इसी कारण से, अधिकांश तार इस अर्थ में जटिल होते हैं कि उन्हें महत्वपूर्ण रूप से संकुचित नहीं किया जा सकता है | उनका K(s) |s|, बिट्स में s की लंबाई से बहुत छोटा नहीं है। इसे स्पष्ट बनाने के लिए, n का मान ठीक करें। वहाँ लंबाई n के 2 </super> बिट स्ट्रिंग्स की बिटस्ट्रिंग्स के स्थान पर समान वितरण (असतत) संभाव्यता वितरण बिल्कुल सामान वजन 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 से स्वतंत्र है।

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

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

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

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

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

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

प्रमाण:

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

function NthProof(int n)

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

function NthProofProvesComplexityFormula(int n)

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

function StringNthProof(int n)

function ComplexityLowerBoundNthProof(int n)

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

function GenerateProvablyComplexString(int n)
    for i = 1 to infinity:
        if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
            return StringNthProof(i)

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

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

GenerateProvablyComplexString(n0)

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

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

	K(s)
≥	n0		के निर्माण द्वारा GenerateProvablyComplexString
>	U+log2(n0)		n0 के विकल्प से
≥	K(s)		चूँकि s को प्रोग्राम द्वारा उस लंबाई के साथ वर्णित किया गया था

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

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

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

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

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

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

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

See also: एल्गोरिथम यादृच्छिकता

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

परिमित वर्णमाला से अनंत अनुक्रमों के लिए यादृच्छिकता की धारणा को परिभाषित करने के लिए इस परिभाषा को विस्तारित किया जा सकता है। इन एल्गोरिदमिक रूप से यादृच्छिक अनुक्रमों को तीन समान विधियों से परिभाषित किया जा सकता है। एक तरह से माप सिद्धांत के प्रभावी एनालॉग का उपयोग करता है | दूसरा प्रभावी मार्टिंगेल (संभाव्यता सिद्धांत) का उपयोग करता है। तीसरा विधि अनंत अनुक्रम को यादृच्छिक होने के लिए परिभाषित करता है | यदि इसके प्रारंभिक खंडों की उपसर्ग-मुक्त कोल्मोगोरोव जटिलता पर्याप्त तेज़ी से बढ़ती है | एक स्थिर 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.