डेटा कॉम्प्रेशन बद्दल विरोधाभास

डेटा कॉम्प्रेशनची समस्या, त्याच्या सर्वात सोप्या स्वरूपात, संख्या आणि त्यांच्या नोटेशनशी संबंधित असू शकते. संख्या अंकांद्वारे दर्शवल्या जाऊ शकतात ("अकरा" संख्या 11 साठी), गणितीय अभिव्यक्ती ("विसाव्या मध्ये दोन" 1048576 साठी), स्ट्रिंग एक्सप्रेशन ("पाच नऊ" 99999 साठी), योग्य नावे ("श्वापदाची संख्या" ६६६ साठी, "ट्युरिंगच्या मृत्यूचे वर्ष" 1954 साठी), किंवा त्याचे अनियंत्रित संयोजन. कोणताही पदनाम योग्य आहे ज्याद्वारे संवादक स्पष्टपणे ठरवू शकतो की आपण कोणत्या क्रमांकाबद्दल बोलत आहोत. अर्थात, तुमच्या संभाषणकर्त्याला सांगा "आठांचा गुणज" समतुल्य नोटेशनपेक्षा अधिक कार्यक्षम "चाळीस हजार तीनशे वीस". येथे एक तार्किक प्रश्न उद्भवतो: दिलेल्या संख्येसाठी सर्वात लहान नोटेशन काय आहे?

तत्त्वज्ञ बर्ट्रांड रसेल यांनी 1908 मध्ये प्रकाशित केले "बेरीचा विरोधाभास", जे विरुद्ध बाजूने क्रमांक नोटेशनच्या समस्येला स्पर्श करते: ऐंशी अक्षरांची आवश्यकता नसलेली सर्वात लहान संख्या कोणती?
अशी संख्या अस्तित्वात असणे आवश्यक आहे: ऐंशी रशियन अक्षरे आणि रिक्त स्थानांमधून आपण केवळ 3480 पदनाम बनवू शकता, याचा अर्थ असा की ऐंशी अक्षरे वापरुन आपण 3480 पेक्षा जास्त संख्या नियुक्त करू शकत नाही. याचा अर्थ असा की अशा प्रकारे 3480 पेक्षा जास्त नसलेली विशिष्ट संख्या नियुक्त करणे अशक्य आहे.

याचा अर्थ हा क्रमांक पदनामाशी सुसंगत असेल "सर्वात लहान संख्या ज्यासाठी ऐंशी अक्षरे पुरेसे नाहीत", ज्यात फक्त 78 अक्षरे आहेत! एकीकडे, ही संख्या अस्तित्वात असणे आवश्यक आहे; दुसरीकडे, जर ही संख्या अस्तित्वात असेल, तर त्याचे पदनाम त्याच्याशी संबंधित नाही. विरोधाभास!

हा विरोधाभास नाकारण्याचा सर्वात सोपा मार्ग म्हणजे मौखिक नोटेशन्सच्या अनौपचारिकतेचा संदर्भ घेणे. जसे की, नोटेशनमध्ये केवळ विशिष्टपणे परिभाषित केलेल्या अभिव्यक्तींच्या संचाला परवानगी दिली असेल तर "सर्वात लहान संख्या ज्यासाठी ऐंशी अक्षरे पुरेसे नाहीत" एक वैध नोटेशन नसेल, तर व्यावहारिकदृष्ट्या उपयुक्त नोटेशन्स जसे "आठांचा गुणज" स्वीकार्य राहील.

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

बेरीच्या विरोधाभासाच्या ऐवजी, आम्ही आता एक समान विचार करू शकतो: एक किलोबाइट प्रोग्राम आउटपुट करण्यासाठी पुरेसा नसलेली सर्वात लहान संख्या कोणती आहे?

आम्ही पूर्वीप्रमाणेच तर्क करू: 2561024 किलोबाइट मजकूर आहेत, याचा अर्थ किलोबाइट प्रोग्रामद्वारे 2561024 पेक्षा जास्त संख्या आउटपुट होऊ शकत नाहीत. याचा अर्थ असा की 2561024 पेक्षा जास्त नसलेली विशिष्ट संख्या अशा प्रकारे मिळवता येत नाही.

पण पायथनमध्ये एक प्रोग्राम लिहू या जो सर्व संभाव्य किलोबाइट मजकूर तयार करतो, ते कार्यान्वित करण्यासाठी चालवतो आणि जर त्यांनी एक नंबर आउटपुट केला तर हा नंबर पोहोचण्यायोग्य लोकांच्या शब्दकोशात जोडतो. सर्व 2561024 शक्यता तपासल्यानंतर, कितीही वेळ लागला तरी, प्रोग्राम डिक्शनरीमधून गहाळ असलेली सर्वात लहान संख्या शोधतो आणि ती संख्या मुद्रित करतो. असे दिसते की असा प्रोग्राम एका किलोबाइट कोडमध्ये बसेल - आणि एक किलोबाइट प्रोग्रामद्वारे आउटपुट होऊ शकत नाही अशी संख्या आउटपुट करेल!

आता पकड काय आहे? यापुढे नोटेशनच्या अनौपचारिकतेचे श्रेय दिले जाऊ शकत नाही!

आमच्या प्रोग्रामला कार्य करण्यासाठी खगोलीय प्रमाणात मेमरीची आवश्यकता असेल - 2561024 घटकांचा एक शब्दकोश (किंवा बिट अॅरे) - तर तुम्ही त्याशिवाय तेच करू शकता: प्रत्येक 2561024 क्रमांकांसाठी, बदल्यात , सर्व 2561024 संभाव्य प्रोग्राममधून जा, जोपर्यंत योग्य नाही. असा शोध बराच काळ टिकेल हे काही फरक पडत नाही: संख्या आणि प्रोग्राममधील (2561024) 2 पेक्षा कमी जोड्या तपासल्यानंतर, तो संपेल आणि तो खूप प्रिय क्रमांक सापडेल.

की संपणार नाही? खरंच, प्रयत्न केले जातील अशा सर्व कार्यक्रमांमध्ये, तेथे असेल while True: pass (आणि त्याचे कार्यात्मक analogues) - आणि प्रकरण अशा प्रोग्रामची चाचणी करण्यापेक्षा पुढे जाणार नाही!

बेरीच्या विरोधाभासाच्या विपरीत, जेथे कॅच नोटेशनच्या अनौपचारिकतेमध्ये होता, दुसऱ्या प्रकरणात आमच्याकडे एक चांगली प्रच्छन्न सुधारणा आहे "समस्या थांबवणे". वस्तुस्थिती अशी आहे की मर्यादित वेळेत प्रोग्राममधून त्याचे आउटपुट निश्चित करणे अशक्य आहे. विशेषतः, कोल्मोगोरोव्हची जटिलता अगणित: दिलेल्या संख्येसाठी, हा क्रमांक मुद्रित करणार्‍या सर्वात लहान प्रोग्रामची लांबी शोधण्याची परवानगी देणारा कोणताही अल्गोरिदम नाही; याचा अर्थ बेरीच्या समस्येवर कोणताही उपाय नाही - दिलेल्या संख्येसाठी सर्वात लहान मौखिक पदनामाची लांबी शोधणे.

स्त्रोत: www.habr.com