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

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

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

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

सिंहावलोकन

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

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

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

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

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

इतिहास

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

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

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

Main article: Kolmogorov complexity

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

Main article: Algorithmically random sequence

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

• 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)