தரவு சுருக்கத்தின் சிக்கல், அதன் எளிமையான வடிவத்தில், எண்கள் மற்றும் அவற்றின் குறியீடுகளுடன் தொடர்புடையதாக இருக்கலாம். எண்களை எண்களால் குறிக்கலாம் ("பதினொரு" எண் 11 க்கு), கணித வெளிப்பாடுகள் ("இருபதில் இரண்டு" 1048576க்கு), சர வெளிப்பாடுகள் ("ஐந்து ஒன்பதுகள்" 99999க்கு), சரியான பெயர்கள் ("மிருகத்தின் எண்ணிக்கை" 666க்கு, "டூரிங் இறந்த ஆண்டு" 1954), அல்லது அதன் தன்னிச்சையான சேர்க்கைகள். எந்தவொரு பதவியும் பொருத்தமானது, இதன் மூலம் நாம் எந்த எண்ணைப் பற்றி பேசுகிறோம் என்பதை உரையாசிரியர் தெளிவாக தீர்மானிக்க முடியும். வெளிப்படையாக, உங்கள் உரையாசிரியரிடம் சொல்லுங்கள் "எட்டு காரணி" சமமான குறியீட்டை விட திறமையானது "நாற்பதாயிரத்து முந்நூற்று இருபது". இங்கே ஒரு தர்க்கரீதியான கேள்வி எழுகிறது: கொடுக்கப்பட்ட எண்ணுக்கான குறுகிய குறியீடு எது?
தத்துவஞானி பெர்ட்ராண்ட் ரஸ்ஸல் 1908 இல் வெளியிட்டார் , இது எதிர் பக்கத்தில் இருந்து எண் குறிப்பின் சிக்கலைத் தொடுகிறது: எண்பது எழுத்துக்கள் தேவைப்படாத மிகச்சிறிய எண் எது?
அத்தகைய எண் இருக்க வேண்டும்: எண்பது ரஷ்ய எழுத்துக்கள் மற்றும் இடங்களிலிருந்து நீங்கள் 3480 பதவிகளை மட்டுமே உருவாக்க முடியும், அதாவது எண்பது எழுத்துக்களைப் பயன்படுத்தி நீங்கள் 3480 எண்களுக்கு மேல் நியமிக்க முடியாது. இந்த வழியில் ஒரு குறிப்பிட்ட எண்ணை 3480 க்கு மேல் குறிப்பிட முடியாது என்பதே இதன் பொருள்.
இதன் பொருள் இந்த எண் பதவிக்கு ஒத்திருக்கும் "எண்பது எழுத்துக்கள் போதுமானதாக இல்லாத மிகச்சிறிய எண்", இதில் 78 எழுத்துக்கள் மட்டுமே உள்ளன! ஒருபுறம், இந்த எண் இருக்க வேண்டும்; மறுபுறம், இந்த எண் இருந்தால், அதன் பதவி அதற்கு பொருந்தாது. முரண்!
இந்த முரண்பாட்டை நிராகரிப்பதற்கான எளிதான வழி, வாய்மொழி குறிப்புகளின் முறைசாரா தன்மையைக் குறிப்பிடுவதாகும். குறிப்பில் குறிப்பாக வரையறுக்கப்பட்ட வெளிப்பாடுகள் மட்டுமே அனுமதிக்கப்பட்டால், அது போல "எண்பது எழுத்துக்கள் போதுமானதாக இல்லாத மிகச்சிறிய எண்" சரியான குறியீடாக இருக்காது, அதேசமயம் நடைமுறையில் பயனுள்ள குறியீடுகள் போன்றவை "எட்டு காரணி" ஏற்றுக்கொள்ளக்கூடியதாக இருக்கும்.
எண்களில் செயல்களின் வரிசையை (அல்காரிதம்) விவரிக்க முறையான வழிகள் உள்ளதா? உள்ளன, மற்றும் ஏராளமாக - அவை நிரலாக்க மொழிகள் என்று அழைக்கப்படுகின்றன. வாய்மொழிக் குறிப்புகளுக்குப் பதிலாக, தேவையான எண்களைக் காண்பிக்கும் நிரல்களைப் பயன்படுத்துவோம் (எடுத்துக்காட்டாக, பைத்தானில்). எடுத்துக்காட்டாக, ஐந்து ஒன்பதுகளுக்கு நிரல் பொருத்தமானது print("9"*5). கொடுக்கப்பட்ட எண்ணுக்கான குறுகிய திட்டத்தில் நாங்கள் தொடர்ந்து ஆர்வமாக இருப்போம். அத்தகைய திட்டத்தின் நீளம் அழைக்கப்படுகிறது எண்கள்; கொடுக்கப்பட்ட எண்ணை சுருக்கக்கூடிய கோட்பாட்டு வரம்பு இது.
பெர்ரியின் முரண்பாட்டிற்குப் பதிலாக, நாம் இப்போது இதேபோன்ற ஒன்றைக் கருத்தில் கொள்ளலாம்: ஒரு கிலோபைட் நிரல் வெளியீட்டிற்கு போதுமானதாக இல்லாத மிகச்சிறிய எண் எது?
முன்பு இருந்ததைப் போலவே நாங்கள் நியாயப்படுத்துவோம்: 2561024 கிலோபைட் உரைகள் உள்ளன, அதாவது கிலோபைட் நிரல்களால் 2561024 எண்களுக்கு மேல் வெளியிட முடியாது. இதன் பொருள் 2561024 ஐ விட ஒரு குறிப்பிட்ட எண்ணை இந்த வழியில் பெற முடியாது.
ஆனால் பைத்தானில் ஒரு நிரலை எழுதுவோம், அது சாத்தியமான அனைத்து கிலோபைட் உரைகளையும் உருவாக்குகிறது, அவற்றை செயல்படுத்துவதற்கு இயக்குகிறது, மேலும் அவை எண்ணை வெளியிட்டால், இந்த எண்ணை அணுகக்கூடியவற்றின் அகராதியில் சேர்க்கிறது. அனைத்து 2561024 சாத்தியங்களையும் சரிபார்த்த பிறகு, அது எவ்வளவு நேரம் எடுத்தாலும், நிரல் அகராதியிலிருந்து விடுபட்ட சிறிய எண்ணைத் தேடி, அந்த எண்ணை அச்சிடுகிறது. அத்தகைய நிரல் ஒரு கிலோபைட் குறியீட்டில் பொருந்தும் என்பது தெளிவாகத் தெரிகிறது - மேலும் ஒரு கிலோபைட் நிரலால் வெளியிட முடியாத எண்ணை வெளியிடும்!
இப்போது என்ன பிடிப்பு? குறிப்பேட்டின் முறைசாரா தன்மைக்கு இனி இது காரணமாக இருக்க முடியாது!
2561024 உறுப்புகளின் அகராதி (அல்லது பிட் வரிசை) - எங்கள் நிரல் வேலை செய்ய வானியல் அளவு நினைவகம் தேவைப்படும் என்பதில் நீங்கள் குழப்பமடைந்தால், அது இல்லாமல் நீங்கள் அதையே செய்யலாம்: ஒவ்வொரு 2561024 எண்களுக்கும். , அனைத்து 2561024 சாத்தியமான நிரல்களையும் பார்க்கவும், பொருத்தமானது எதுவும் இல்லை. அத்தகைய தேடல் மிக நீண்ட காலம் நீடிக்கும் என்பது ஒரு பொருட்டல்ல: எண் மற்றும் நிரலிலிருந்து (2561024) 2 ஜோடிகளுக்குக் குறைவாகச் சரிபார்த்த பிறகு, அது முடிவடையும் மற்றும் மிகவும் நேசத்துக்குரிய எண்ணைக் கண்டுபிடிக்கும்.
அல்லது அது முடிவடையாதா? உண்மையில், முயற்சி செய்யப்படும் அனைத்து நிரல்களிலும், இருக்கும் while True: pass (மற்றும் அதன் செயல்பாட்டு ஒப்புமைகள்) - மற்றும் அத்தகைய நிரலை சோதிப்பதை விட விஷயம் மேலே செல்லாது!
பெர்ரியின் முரண்பாட்டைப் போலல்லாமல், குறிமுறையின் முறைசாரா நிலையில் கேட்ச் இருந்தது, இரண்டாவது வழக்கில் நாம் நன்கு மாறுவேடமிட்ட சீர்திருத்தத்தைக் கொண்டுள்ளோம். . ஒரு நிரலிலிருந்து அதன் வெளியீட்டை வரையறுக்கப்பட்ட நேரத்தில் தீர்மானிக்க இயலாது என்பதே உண்மை. குறிப்பாக, Kolmogorov சிக்கலானது : கொடுக்கப்பட்ட எண்ணுக்கு, இந்த எண்ணை அச்சிடும் மிகக் குறுகிய நிரலின் நீளத்தைக் கண்டறிய அனுமதிக்கும் வழிமுறை எதுவும் இல்லை; அதாவது பெர்ரியின் பிரச்சனைக்கு தீர்வு இல்லை - கொடுக்கப்பட்ட எண்ணுக்கான குறுகிய வாய்மொழி பதவியின் நீளத்தைக் கண்டறிய.
ஆதாரம்: www.habr.com