Ang problema ng data compression, sa pinakasimpleng anyo nito, ay maaaring nauugnay sa mga numero at kanilang mga notasyon. Ang mga numero ay maaaring tukuyin ng mga numero ("labing isang" para sa bilang 11), mga ekspresyong matematika ("dalawa sa ikadalawampu" para sa 1048576), string expression ("limang siyam" para sa 99999), mga tamang pangalan ("bilang ng halimaw" para sa 666, "taon ng pagkamatay ni Turing" para sa 1954), o mga di-makatwirang kumbinasyon nito. Ang anumang pagtatalaga ay angkop kung saan malinaw na matukoy ng interlocutor kung anong numero ang pinag-uusapan natin. Malinaw, sabihin sa iyong kausap "factorial ng walo" mas mahusay kaysa sa katumbas na notasyon "apatnapung libo tatlong daan dalawampu". Isang lohikal na tanong ang lumitaw dito: ano ang pinakamaikling notasyon para sa isang naibigay na numero?
Ang pilosopo na si Bertrand Russell ay inilathala noong 1908 , na tumatalakay sa isyu ng notasyon ng numero mula sa kabilang panig: Ano ang pinakamaliit na bilang na hindi nangangailangan ng walumpung titik?
Ang nasabing numero ay dapat na umiiral: mula sa walumpung Russian na mga titik at mga puwang maaari kang bumuo lamang ng 3480 na mga pagtatalaga, na nangangahulugang gamit ang walumpung titik maaari kang magtalaga ng hindi hihigit sa 3480 na mga numero. Nangangahulugan ito na imposibleng magtalaga ng isang tiyak na numero na hindi hihigit sa 3480 sa ganitong paraan.
Nangangahulugan ito na ang numerong ito ay tumutugma sa pagtatalaga "ang pinakamaliit na bilang kung saan hindi sapat ang walumpung titik", na may 78 letra lamang! Sa isang banda, ang numerong ito ay dapat na umiiral; sa kabilang banda, kung ang numerong ito ay umiiral, kung gayon ang pagtatalaga nito ay hindi tumutugma dito. Kabalintunaan!
Ang pinakamadaling paraan upang bale-walain ang kabalintunaan na ito ay ang sumangguni sa impormal ng mga notasyong pandiwa. Tulad ng, kung isang partikular na tinukoy na hanay ng mga expression lamang ang pinapayagan sa notasyon, kung gayon "ang pinakamaliit na bilang kung saan hindi sapat ang walumpung titik" ay hindi isang wastong notasyon, samantalang ang mga praktikal na kapaki-pakinabang na notasyon tulad ng "factorial ng walo" ay mananatiling katanggap-tanggap.
Mayroon bang mga pormal na paraan upang ilarawan ang pagkakasunud-sunod (algorithm) ng mga aksyon sa mga numero? Mayroong, at sa kasaganaan - sila ay tinatawag na mga programming language. Sa halip na verbal notation, gagamit kami ng mga program (halimbawa, sa Python) na nagpapakita ng mga kinakailangang numero. Halimbawa, para sa limang siyam ang programa ay angkop print("9"*5). Patuloy kaming magiging interesado sa pinakamaikling programa para sa isang naibigay na numero. Ang haba ng naturang programa ay tinatawag numero; ito ay ang teoretikal na limitasyon kung saan ang isang naibigay na numero ay maaaring i-compress.
Sa halip na kabalintunaan ni Berry, maaari na nating isaalang-alang ang isang katulad: Ano ang pinakamaliit na bilang na hindi sapat na i-output ng isang kilobyte program?
Mangangatuwiran kami sa parehong paraan tulad ng dati: mayroong 2561024 kilobyte na mga teksto, na nangangahulugan na hindi hihigit sa 2561024 na mga numero ang maaaring i-output ng mga kilobyte na programa. Nangangahulugan ito na ang isang tiyak na numero na hindi hihigit sa 2561024 ay hindi maaaring makuha sa ganitong paraan.
Ngunit sumulat tayo ng isang programa sa Python na bumubuo ng lahat ng posibleng mga tekstong kilobyte, pinapatakbo ang mga ito para sa pagpapatupad, at kung maglalabas sila ng isang numero, pagkatapos ay idaragdag ang numerong ito sa diksyunaryo ng mga maaabot. Pagkatapos suriin ang lahat ng 2561024 na posibilidad, gaano man katagal, hinahanap ng programa ang pinakamaliit na numerong nawawala sa diksyunaryo at ini-print ang numerong iyon. Tila halata na ang naturang programa ay magkasya sa isang kilobyte ng code - at maglalabas ng mismong bilang na hindi maaaring i-output ng isang kilobyte na programa!
Ano ang huli ngayon? Hindi na ito maiuugnay sa pagiging impormal ng notasyon!
Kung nalilito ka sa katotohanan na ang aming programa ay mangangailangan ng astronomical na dami ng memory upang gumana - isang diksyunaryo (o bit array) ng 2561024 elemento - pagkatapos ay magagawa mo ang parehong bagay nang wala ito: para sa bawat isa sa 2561024 na mga numero, sa turn , dumaan sa lahat ng 2561024 na posibleng programa, hanggang sa walang angkop. Hindi mahalaga na ang naturang paghahanap ay tatagal nang napakatagal: pagkatapos suriin ang mas mababa sa (2561024)2 pares mula sa numero at sa programa, ito ay magtatapos at mahahanap ang napakamahal na numerong iyon.
O hindi na matatapos? Sa katunayan, sa lahat ng mga programa na susubukan, magkakaroon while True: pass (at ang mga functional analogue nito) - at ang bagay ay hindi lalampas sa pagsubok ng naturang programa!
Hindi tulad ng kabalintunaan ni Berry, kung saan ang catch ay nasa impormal ng notasyon, sa pangalawang kaso mayroon kaming isang mahusay na disguised reformulation . Ang katotohanan ay imposibleng matukoy ang output nito mula sa isang programa sa isang takdang panahon. Sa partikular, ang pagiging kumplikado ng Kolmogorov : walang algorithm na magpapahintulot, para sa isang naibigay na numero, upang mahanap ang haba ng pinakamaikling programa na nagpi-print ng numerong ito; na nangangahulugan na walang solusyon sa problema ni Berry - upang mahanap ang haba ng pinakamaikling verbal na pagtatalaga para sa isang naibigay na numero.
Pinagmulan: www.habr.com