Ang problema sa data compression, sa pinakasimple nga porma niini, mahimong may kalabutan sa mga numero ug sa ilang mga notasyon. Ang mga numero mahimong itudlo pinaagi sa mga numero ("onse" para sa numero 11), mga ekspresyon sa matematika ("duha sa ikakawhaan" para sa 1048576), string nga mga ekspresyon ("lima ka siyam" para sa 99999), mga ngalan ("gidaghanon sa mananap" alang sa 666, "tuig sa pagkamatay ni Turing" para sa 1954), o arbitraryong mga kombinasyon niini. Ang bisan unsang pagtawag angayan diin ang interlocutor tin-aw nga mahibal-an kung unsang numero ang among gihisgutan. Dayag nga, sultihi ang imong interlocutor "faktorial sa walo" mas episyente kay sa katumbas nga notasyon "kwarenta ka libo tulo ka gatus ug baynte". Usa ka lohikal nga pangutana ang mitungha dinhi: unsa ang labing mubo nga notasyon alang sa usa ka gihatag nga numero?
Ang pilosopo nga si Bertrand Russell gipatik niadtong 1908 , nga nagtandog sa isyu sa notasyon sa numero gikan sa atbang nga bahin: Unsa ang pinakagamay nga numero nga wala magkinahanglan ug kawaloan ka letra?
Ang ingon nga numero kinahanglan nga anaa: gikan sa kawaloan nga Russian nga mga letra ug mga luna mahimo ka nga makahimo lamang sa 3480 nga mga ngalan, nga nagpasabot nga ang paggamit sa kawaloan ka mga letra mahimo nimong itudlo nga dili molapas sa 3480 nga mga numero. Kini nagpasabot nga imposible ang pagtudlo sa usa ka numero nga dili molapas sa 3480 niining paagiha.
Kini nagpasabot nga kini nga numero motakdo sa designasyon "ang pinakagamay nga numero diin ang kawaloan ka letra dili igo", nga adunay 78 lang ka letra! Sa usa ka bahin, kini nga numero kinahanglan nga anaa; sa laing bahin, kon kini nga numero anaa, nan ang ngalan niini dili katumbas niini. Paradox!
Ang labing sayon ββββnga paagi sa pagsalikway niini nga paradox mao ang paghisgot sa dili pormalidad sa verbal notation. Sama sa, kung ang usa ka piho nga gihubit nga hugpong sa mga ekspresyon gitugotan sa notasyon, nan "ang pinakagamay nga numero diin ang kawaloan ka letra dili igo" dili usa ka balido nga notasyon, samtang ang praktikal nga mapuslanon nga mga notasyon sama sa "faktorial sa walo" magpabilin nga madawat.
Aduna bay pormal nga mga paagi sa paghulagway sa han-ay (algorithm) sa mga aksyon sa mga numero? Adunay, ug sa kadagaya - sila gitawag programming pinulongan. Imbis nga mga notasyon sa pulong, mogamit kami mga programa (pananglitan, sa Python) nga nagpakita sa gikinahanglan nga mga numero. Pananglitan, alang sa lima ka nines ang programa angay print("9"*5). Magpadayon kami nga interesado sa pinakamubo nga programa alang sa gihatag nga numero. Ang gitas-on sa maong programa gitawag mga numero; kini ang teoretikal nga limitasyon diin ang usa ka gihatag nga numero mahimong ma-compress.
Imbis nga paradox ni Berry, mahimo na naton ikonsiderar ang parehas: Unsa ang pinakagamay nga numero nga ang usa ka kilobyte nga programa dili igo aron ma-output?
Mangatarungan kami sa parehas nga paagi sama sa una: adunay 2561024 nga kilobyte nga mga teksto, nga nagpasabut nga dili molapas sa 2561024 nga mga numero ang mahimong ma-output sa mga kilobyte nga programa. Kini nagpasabot nga ang usa ka piho nga numero nga dili molapas sa 2561024 dili makuha niining paagiha.
Apan magsulat kita og usa ka programa sa Python nga nagmugna sa tanang posibleng mga kilobyte nga mga teksto, nagpadagan niini alang sa pagpatuman, ug kung sila nagpagawas sa usa ka numero, unya idugang kini nga numero sa diksyonaryo sa mga maabot. Human masusi ang tanang 2561024 ka posibilidad, bisag unsa kadugay, ang programa mangita sa pinakagamay nga numero nga nawala sa diksyonaryo ug mag-imprenta sa maong numero. Morag klaro nga ang ingon nga programa mohaum sa usa ka kilobyte nga code - ug magpagawas sa mismong gidaghanon nga dili ma-output sa usa ka kilobyte nga programa!
Unsa ang nakuha karon? Dili na kini ikapasangil sa pagka-impormal sa notasyon!
Kung naglibog ka sa kamatuoran nga ang among programa nanginahanglan usa ka astronomical nga kantidad sa memorya aron molihok - usa ka diksyonaryo (o gamay nga array) sa 2561024 nga mga elemento - nan mahimo nimo ang parehas nga butang kung wala kini: alang sa matag usa sa 2561024 nga mga numero, sa baylo , adtoa ang tanang 2561024 nga posibleng mga programa, hangtod nga wala nay angay. Dili igsapayan nga ang ingon nga pagpangita molungtad sa usa ka taas nga panahon: pagkahuman sa pagsusi sa ubos sa (2561024) 2 nga mga pares gikan sa numero ug sa programa, kini matapos ug makit-an ang gimahal kaayo nga numero.
O dili ba kini mahuman? Sa pagkatinuod, taliwala sa tanan nga mga programa nga pagasulayan, adunay while True: pass (ug ang mga analogue nga magamit niini) - ug ang butang dili mopadayon kaysa pagsulay sa ingon nga programa!
Dili sama sa paradox ni Berry, diin ang pagdakop anaa sa informality sa notasyon, sa ikaduha nga kaso kita adunay usa ka maayo nga nagtakuban reformulation . Ang kamatuoran mao nga imposible nga mahibal-an ang output niini gikan sa usa ka programa sa usa ka limitado nga panahon. Sa partikular, Kolmogorov komplikado : walay algorithm nga motugot, alang sa gihatag nga numero, sa pagpangita sa gitas-on sa pinakamubo nga programa nga nag-imprinta niini nga numero; nga nagpasabot nga walay solusyon sa problema ni Berry - sa pagpangita sa gitas-on sa pinakamubo nga verbal designation alang sa usa ka gihatag nga numero.
Source: www.habr.com