एल्गोरिथम सूचना सिद्धांत

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

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

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

अवलोकन

एल्गोरिथम सूचना सिद्धांत मुख्य रूप से स्ट्रिंग (कंप्यूटर विज्ञान) (या अन्य डेटा संरचनाओं) पर जटिलता के उपायों का अध्ययन करता है। चूँकि अधिकांशतः गणितीय वस्तुओं को स्ट्रिंग्स के रूप में वर्णित किया जा सकता है या स्ट्रिंग्स के अनुक्रम की सीमा के रूप में वर्णित किया जा सकता है। इसका उपयोग पूर्णांकों के साथ विभिन्न प्रकार की गणितीय वस्तुओं का अध्ययन करने के लिए किया जा सकता है।

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

इस दृष्टिकोण से एक 3000 पृष्ठ के इनसाइक्लोपीडिया में यथार्थ रूप से पूर्णतयः यादृच्छिक अक्षरों के 3000 पृष्ठों की तुलना में कम जानकारी प्राप्त होती है। इस तथ्य के बाद कि इनसाइक्लोपीडिया कहीं अधिक उपयोगी सिद्ध होता है। ऐसा इसलिए होता है क्योंकि यादृच्छिक अक्षरों के सम्पूर्ण अनुक्रम का पुनर्निर्माण करने के लिए प्रत्येक व्यक्ति को यह पता होना चाहिए कि प्रत्येक अक्षर क्या है। दूसरी ओर यदि प्रत्येक स्वर को इनसाइक्लोपीडिया से हटा दिया जाता है। जिससे अंग्रेजी भाषा का उचित ज्ञान रखने वाला कोई व्यक्ति इसे पुनः बना सकता है। ठीक उसी प्रकार जैसे कोई व्यक्ति संदर्भ और उपस्थित व्यंजनों से वाक्य को पुनः निर्मित कर सकता है।

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

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

इतिहास

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

कोलमोगोरोव जटिलता या एल्गोरिथम जानकारी के कई रूप हैं। सबसे व्यापक रूप से प्रयोग किया जाने वाला स्व-सीमांकन कार्यक्रमों पर आधारित है और मुख्य रूप से लियोनिद लेविन (1974) के कारण है। प्रति मार्टिन-लोफ ने अनंत अनुक्रमों के सूचना सिद्धांत में भी महत्वपूर्ण योगदान प्रदान किया है। ब्लम स्वयंसिद्ध (ब्लम 1967) पर आधारित एल्गोरिथम सूचना सिद्धांत के लिए एक स्वयंसिद्ध दृष्टिकोण मार्क बर्गिन द्वारा एंड्री कोलमोगोरोव (बर्गिन 1982) द्वारा प्रकाशन के लिए प्रस्तुत एक पेपर में प्रस्तुत किया गया था। स्वयंसिद्ध दृष्टिकोण एल्गोरिथम सूचना सिद्धांत में अन्य दृष्टिकोणों को सम्मिलित करता है। एल्गोरिथम जानकारी के स्वयंसिद्ध रूप से परिभाषित उपायों के विशेष स्थितियों के रूप में एल्गोरिथम जानकारी के विभिन्न उपायों को सही करना संभव है। समान प्रमेयों को सिद्ध करने के अतिरिक्त जैसे कि प्रत्येक विशेष माप के लिए मूल व्युत्क्रम प्रमेय, स्वयंसिद्ध सेटिंग में सिद्ध किए गए एक संबंधित प्रमेय से ऐसे सभी परिणामों को से निकालना संभव है। यह गणित में स्वयंसिद्ध दृष्टिकोण का एक सामान्य लाभ प्राप्त होता है। एल्गोरिथम सूचना सिद्धांत के स्वयंसिद्ध दृष्टिकोण को पुस्तक (बर्जिन 2005) में विकसित किया गया था और सॉफ्टवेयर मेट्रिक्स (देबनाथ और बर्गिन, 2003) पर संचालित किया गया था।

सटीक परिभाषाएँ

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

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

Main article: एल्गोरिदमिक रूप से यादृच्छिक अनुक्रम

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

(समुच्चय $\{0,1\}$ के अतिरिक्त अन्य अक्षरों के लिए संबंधित परिभाषाएं बनाई जा सकती हैं।)

विशिष्ट अनुक्रम

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

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

"0101010101010101010101010101010101010101010101010101010101010101"

संक्षिप्त विवरण '01' के 32 दोहराव हैं। जबकि-

"1100100001100001110111101110110011111010010000100101011110010110"

संभवतः स्ट्रिंग को लिखने के अतिरिक्त कोई सरल विवरण नहीं है।

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

एक निकटतम संबंधित धारणा संभावना है कि एक सार्वभौमिक कंप्यूटर यादृच्छिक रूप से चुने गए प्रोग्राम के साथ प्रदर्शित किये जाने पर कुछ स्ट्रिंग x को आउटपुट करता है। यह एल्गोरिद्मिक प्रायिकता एल्गोरिद्मिक सोलोमनॉफ प्रायिकता (एपी) एक औपचारिक प्रकार से प्रेरण की पुरानी दार्शनिक समस्या को संबोधित करने में महत्वपूर्ण है।

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

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

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

यह भी देखें

• Algorithmic probability
• Algorithmically random sequence
• Chaitin's constant
• Chaitin–Kolmogorov randomness
• Computationally indistinguishable
• Distribution ensemble
• Epistemology
• Inductive inference
• Inductive probability
• Invariance theorem
• Kolmogorov complexity
• Minimum description length
• Minimum message length
• Pseudorandom ensemble
• Pseudorandom generator
• Simplicity theory
• Shannon's source coding theorem
• Solomonoff's theory of inductive inference
• Uniform ensemble

बाहरी संबंध

• Algorithmic Information Theory at Scholarpedia
• Chaitin's account of the history of AIT.

अग्रिम पठन

• Blum, M. (1967). "On the Size of Machines". Information and Control. 11 (3): 257–265. doi:10.1016/S0019-9958(67)90546-3.
• Blum, M. (1967). "A Machine-independent Theory of Complexity of Recursive Functions". Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. S2CID 15710280.
• Burgin, M. (1982). "Generalized Kolmogorov complexity and duality in theory of computations". Soviet Math. Dokl. 25 (3): 19–23.
• Burgin, M. (1990). "Generalized Kolmogorov Complexity and other Dual Complexity Measures". Cybernetics. 26 (4): 481–490. doi:10.1007/BF01068189. S2CID 121736453.
• Burgin, M. (2005). Super-recursive algorithms. Monographs in computer science. Springer. ISBN 9780387955698.
• Calude, C.S. (1996). "Algorithmic information theory: Open problems" (PDF). J. UCS. 2 (5): 439–441.
• Calude, C.S. (2013). Information and Randomness: An Algorithmic Perspective. Texts in Theoretical Computer Science. An EATCS Series (2nd ed.). Springer-Verlag. ISBN 9783662049785.
• Chaitin, G.J. (1966). "On the Length of Programs for Computing Finite Binary Sequences". Journal of the Association for Computing Machinery. 13 (4): 547–569. doi:10.1145/321356.321363. S2CID 207698337.
• Chaitin, G.J. (1969). "On the Simplicity and Speed of Programs for Computing Definite Sets of Natural Numbers". Journal of the Association for Computing Machinery. 16 (3): 407–412. doi:10.1145/321526.321530. S2CID 12584692.
• Chaitin, G.J. (1975). "A Theory of Program Size Formally Identical to Information Theory". Journal of the Association for Computing Machinery. 22 (3): 329–340. doi:10.1145/321892.321894. S2CID 14133389.
• Chaitin, G.J. (1977). "Algorithmic information theory". IBM Journal of Research and Development. 21 (4): 350–9. doi:10.1147/rd.214.0350.
• Chaitin, G.J. (1987). Algorithmic Information Theory. Cambridge University Press. ISBN 9780521343060.
• Kolmogorov, A.N. (1965). "Three approaches to the definition of the quantity of information". Problems of Information Transmission (1): 3–11.
• Kolmogorov, A.N. (1968). "Logical basis for information theory and probability theory". IEEE Trans. Inf. Theory. IT-14 (5): 662–4. doi:10.1109/TIT.1968.1054210.
• Levin, L. A. (1974). "Laws of information (nongrowth) and aspects of the foundation of probability theory". Problems of Information Transmission. 10 (3): 206–210.
• Levin, L.A. (1976). "Various Measures of Complexity for Finite Objects (Axiomatic Description)". Soviet Math. Dokl. 17: 522–526.
• Li, M.; Vitanyi, P. (2013). An Introduction to Kolmogorov Complexity and its Applications (2nd ed.). Springer-Verlag. ISBN 9781475726060.
• Solomonoff, R.J. (1960). A Preliminary Report on a General Theory of Inductive Inference (PDF) (Technical report). Cambridge, Mass: Zator Company. ZTB-138.
• Solomonoff, R.J. (1964). "A Formal Theory of Inductive Inference". Information and Control. 7 (1): 1–22. doi:10.1016/S0019-9958(64)90223-2.
• Solomonoff, R.J. (1964). "A Formal Theory of Inductive Inference". Information and Control. 7 (2): 224–254. doi:10.1016/S0019-9958(64)90131-7.
• Solomonoff, R.J. (2009). Emmert-Streib, F.; Dehmer, M. (eds.). Algorithmic Probability: Theory and Applications, Information Theory and Statistical Learning. Springer. ISBN 978-0-387-84815-0.
• Van Lambagen (1989). "Algorithmic Information Theory" (PDF). Journal of Symbolic Logic. 54 (4): 1389–1400. doi:10.1017/S0022481200041153. S2CID 250348327.
• Zurek, W.H. (2018) [1991]. "Algorithmic Information Content, Church-Turing Thesis, physical entropy, and Maxwell's demon, in". Complexity, Entropy and the Physics of Information. Addison-Wesley. pp. 73–89. ISBN 9780429982514.
• Zvonkin, A.K. and Levin, L. A. (1970). "The Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms". Russian Mathematical Surveys. 256 (6): 83–124. Bibcode:1970RuMaS..25...83Z. doi:10.1070/RM1970v025n06ABEH001269. S2CID 250850390.{{cite journal}}: CS1 maint: multiple names: authors list (link)