सूचना दूरी

सूचना दूरी दो परिमित वस्तुओं के बीच की दूरी है जो सबसे छोटे कार्यक्रम में बिट्स की संख्या के रूप में व्यक्त की जाती है तथा यह एक वस्तु को दूसरी वस्तु या इसके विपरीत सार्वभौमिक कंप्यूटर में बदल देती है यह जटिलता का विस्तार है इसमें एकल परिमित वस्तु की कोलमोगोरोव जटिलता उस वस्तु की जानकारी है जो परिमित वस्तुओं की एक जोड़ी के बीच की सूचना दूरी एक वस्तु से या इसके विपरीत जाने के लिए आवश्यक न्यूनतम जानकारी है सूचना दूरी को पहली बार में परिभाषित और जांच की गई थी ऊष्मागतिकीय सिद्धांतों पर आधारित यह सामान्यीकृत संपीड़न दूरी और सामान्यीकृत दूरी में लागू होता है।

गुण

औपचारिक रूप से सूचना दूरी के $ID(x,y)$ बीच में $x$ और $y$ द्वारा परिभाषित किया गया है

$ID(x,y)=\min\{|p|:p(x)=y\;\&\;p(y)=x\},$

साथ $p$ सार्वभौमिक कंप्यूटर के लिए एक परिमित बाइनरी कार्यक्रम इनपुट के रूप में बाइनरी को में परिभाषित करें इससे यह सिद्ध है कि$ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})$ साथ

$E(x,y)=\max\{K(x\mid y),K(y\mid x)\},$ जहाँ $K(\cdot \mid \cdot )$ कोलमोगोरॉव जटिलता है जिसे उपसर्ग द्वारा परिभाषित किया गया है।

सार्वभौमिकता

सार्वभौमिकता ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो जैसे $D(x,y)$ जो घनत्व की स्थिति को संतुष्ट करता है

$\sum _{x:x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y:y\neq x}2^{-D(x,y)}\leq 1,$

यह अप्रासंगिक दूरियों को बाहर करता है जैसे $D(x,y)={\frac {1}{2}}$ के लिए $x\neq y$ यह इस बात का ध्यान रखता है कि यदि दूरी बढ़ती है तो दी गई वस्तु की उस दूरी के भीतर वस्तुओं की संख्या बढ़ती है तो $D\in \Delta$ तब $E(x,y)\leq D(x,y)$ यह एक निरंतर योगात्मक शब्द तक की दूरी संभाव्यता अभिव्यक्तियाँ सूचना सममित में पहला वर्ग है जिसे सार्वभौमिकता संपत्ति के रूप में जाना जा सकता है।

मीट्रिक

दूरी $E(x,y)$ योज्य तक एक प्रवेशिका स्थान है जो $O(\log .\max\{K(x\mid y),K(y\mid x)\})$ प्रवेशिका 1981 में हान द्वारा दिखाया गया कि प्रवेशिका का संभाव्य संस्करण में अद्वितीय है।

अधिकतम अतिच्छादन

अगर $E(x,y)=K(x\mid y)$ एक कार्यक्रम होता है तो $p$ लंबाई $K(x\mid y)$ में परिवर्तित हो जाता है $y$ को $x$ और एक कार्यक्रम $q$ लंबाई का $K(y\mid x)-K(x\mid y)$ ऐसा रूपांतरण है कि कार्यक्रम $qp$ धर्मान्तरित $x$ तथा $y$.अर्थात दो वस्तुओं के बीच परिवर्तित होने वाले सबसे छोटे कार्यक्रमों को अधिकतम अतिव्यापी बनाया जा सकता है $K(x\mid y)\leq K(y\mid x)$ इसे एक कार्यक्रम में विभाजित किया जा सकता है जो बहुविकल्पीय को परिवर्तित करता है इसमें $x$ वस्तु के लिए $y$और दूसरा कार्यक्रम जो पहले धर्मान्तरित के साथ जुड़ा हुआ है जैसे $y$ तथा $x$ जबकि इन दो कार्यक्रमों का संयोजन इन वस्तुओं के बीच परिवर्तित करने के लिए सबसे छोटा कार्यक्रम है।

न्यूनतम अतिच्छादन

कार्यक्रम को वस्तुओं के बीच बदलने के लिए $x$ और $y$ न्यूनतम अतिच्छादन के लिए भी बनाया जा सकता है इसमें एक कार्यक्रम होता है जहाँ $p$ लंबाई$O(\log(\max\{K(x\mid y),K(y\mid x)\}))$ है यहाँ $y$ तथा $x$ छोटी जटिलता है जब $x$ ज्ञात है तो ($K(p\mid x)\approx 0$).जबकि हमारे पास दो वस्तुओं का आदान-प्रदान करने के लिए दूसरा कार्यक्रम है इसमें शैन्य सूचना सिद्धांत और कोलमोगोरोव की जटिलता की समानता को ध्यान में रखते हुए कोई कह सकता है कि यह परिणाम स्वीडन वुल्फ और कोर्नर इनरे सिज्जार मॉर्टन प्रमेय के समानता है।

अनुप्रयोग

व्यावहारिक

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

संबंधित साहित्य

• Arkhangel'skii, A. V.; Pontryagin, L. S. (1990), General Topology I: Basic Concepts and Constructions Dimension Theory, Encyclopaedia of Mathematical Sciences, Springer, ISBN 3-540-18178-4

श्रेणी:सांख्यिकीय दूरी