डेटा संपीड़न विरोधाभास

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

1908 में दार्शनिक बर्ट्रेंड रसेल ने "बेरी विरोधाभास" प्रकाशित किया , जो विपरीत दिशा में संख्याओं के अंकन के मुद्दे को संबोधित करता है: यह इंगित करने के लिए सबसे छोटी संख्या क्या है जो अस्सी अक्षर पर्याप्त नहीं हैं?
इस तरह की संख्या मौजूद होनी चाहिए: अस्सी रूसी पत्रों और स्थानों में से आप कुल 34 ⁸⁰ पदनाम बना सकते हैं, जिसका अर्थ है कि अस्सी अक्षरों का उपयोग करके आप 34 से अधिक ⁸⁰ संख्याओं को नामित कर सकते हैं। इसलिए, एक निश्चित संख्या, 34 ⁸⁰ से अधिक नहीं है, इस तरह से नामित नहीं किया जा सकता है।

इसका अर्थ है कि पदनाम "सबसे छोटी संख्या जिसके लिए अस्सी अक्षर पर्याप्त नहीं हैं" इस संख्या के अनुरूप होंगे, जिसमें केवल 78 अक्षर हैं! एक ओर, यह संख्या मौजूद होनी चाहिए; दूसरी ओर, यदि यह संख्या मौजूद है, तो इसका पदनाम इसके अनुरूप नहीं है। विरोधाभास!

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

क्या संख्याओं पर क्रियाओं के अनुक्रम (एल्गोरिथम) का वर्णन करने के लिए औपचारिक तरीके हैं? वहाँ हैं, और बहुतायत में - उन्हें प्रोग्रामिंग भाषा कहा जाता है। मौखिक संकेतन के बजाय, हम आवश्यक संख्याओं को मुद्रित करने वाले कार्यक्रमों (उदाहरण के लिए, पायथन में) का उपयोग करेंगे। उदाहरण के लिए, पांच नाइन के लिए, print("9"*5) प्रोग्राम print("9"*5) उपयुक्त है। हम दिए गए नंबर के लिए सबसे कम कार्यक्रम में रुचि लेते रहेंगे। ऐसे कार्यक्रम की लंबाई को संख्या की कोलमोगोरोव जटिलता कहा जाता है; यह सैद्धांतिक सीमा है जिसके लिए किसी संख्या को संपीड़ित किया जा सकता है।

बेरी विरोधाभास के बजाय, अब एक समान विचार कर सकते हैं: सबसे छोटी संख्या क्या है जिसके लिए किलोबाइट कार्यक्रम पर्याप्त नहीं है?

हम पहले की तरह ही बहस करेंगे: ^256,1024 किलोबाइट ग्रंथ हैं, जिसका अर्थ है कि किलोबाइट कार्यक्रमों में ^256,224 से अधिक संख्याएं प्रदर्शित नहीं की जा सकती हैं। इसका अर्थ है कि एक निश्चित संख्या, 256 ¹⁰²⁴ से अधिक नहीं, इस तरह से कटौती नहीं की जा सकती।

लेकिन हम पायथन में एक कार्यक्रम लिखते हैं जो सभी संभावित किलोबाइट ग्रंथों को उत्पन्न करता है, उन्हें निष्पादन के लिए लॉन्च करता है, और यदि वे एक निश्चित संख्या को प्रिंट करते हैं, तो यह इस संख्या को पहुंच योग्य शब्दकोष में जोड़ता है। सभी 256 ¹⁰²⁴ संभावनाओं की जांच करने के बाद, चाहे कितना भी समय लगे - कार्यक्रम सबसे छोटी संख्या के लिए दिखता है जो शब्दकोश में नहीं है और इस संख्या को प्रदर्शित करता है। यह स्पष्ट लगता है कि इस तरह के एक कार्यक्रम कोड किलोबाइट में फिट होगा - और बहुत संख्या में आउटपुट करेगा जो कि किलोबाइट प्रोग्राम में प्रदर्शित नहीं किया जा सकता है!

अब क्या पकड़ है? इसे अब नोटेशन की अनौपचारिकता के लिए जिम्मेदार नहीं ठहराया जा सकता है!

यदि आप भ्रमित हैं कि हमारे कार्यक्रम को काम करने के लिए स्मृति की एक खगोलीय राशि की आवश्यकता होगी - 256 ¹⁰²⁴ तत्वों का एक शब्दकोश (या बिटमैप) - तो आप इसके बिना भी ऐसा कर सकते हैं: प्रत्येक 256 ¹⁰²⁴ संख्याओं के लिए, सभी 256 ¹⁰²⁴ संभव के माध्यम से पुनरावृति कार्यक्रम जब तक एक उपयुक्त नहीं मिला। इससे कोई फर्क नहीं पड़ता कि इस तरह की गणना बहुत लंबे समय तक चलेगी: संख्या और कार्यक्रम से कम (256 ¹⁰²⁴ ) ² जोड़े की जांच करने के बाद, यह समाप्त हो जाएगा, और यह बहुत पोषित संख्या पाएगा।

या खत्म नहीं होगा? वास्तव में, उन सभी कार्यक्रमों के बीच, जिन्हें आज़माया जाएगा, वहीं होगा while True: pass (और उसके कार्यात्मक समकक्ष) - और चीजें इस तरह के कार्यक्रम की जांच से परे नहीं होंगी!

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