ഡാറ്റ കംപ്രഷൻ സംബന്ധിച്ച വിരോധാഭാസങ്ങൾ

ഡാറ്റ കംപ്രഷൻ പ്രശ്നം, അതിന്റെ ഏറ്റവും ലളിതമായ രൂപത്തിൽ, അക്കങ്ങളുമായും അവയുടെ നൊട്ടേഷനുകളുമായും ബന്ധപ്പെട്ടിരിക്കുന്നു. സംഖ്യകളെ അക്കങ്ങളാൽ സൂചിപ്പിക്കാം ("പതിനൊന്ന്" സംഖ്യ 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