Pwoblèm nan konpresyon done, nan fòm ki pi senp li yo, ka gen rapò ak nimewo ak notasyon yo. Nimewo yo ka endike pa nimerik ("onz" pou nimewo 11), ekspresyon matematik ("de nan ventyèm lan" pou 1048576), ekspresyon fisèl ("senk nèf" pou 99999), non pwòp ("kantite bèt la" pou 666, "ane lanmò Turing" pou 1954), oswa konbinezon abitrè ladan yo. Nenpòt deziyasyon apwopriye pa ki entèrlokuteur a ka klèman detèmine ki nimewo nou ap pale. Li evidan, di entèrlokuteur ou a "faktè nan uit" pi efikas pase notasyon ekivalan "karant mil twasan ven". Yon kesyon lojik rive isit la: ki notasyon ki pi kout pou yon nimewo bay?
Filozòf Bertrand Russell te pibliye an 1908 , ki manyen pwoblèm nan notasyon nimewo soti nan bò opoze a: Ki pi piti nimewo ki pa mande katreven lèt?
Yon nimewo sa yo dwe egziste: soti nan katreven lèt Ris ak espas ou ka fè moute sèlman 3480 deziyasyon, ki vle di ke lè w itilize katreven lèt ou ka deziyen pa plis pase 3480 nimewo. Sa vle di ke li enposib deziyen yon sèten nimewo pa plis pase 3480 nan fason sa a.
Sa vle di nimewo sa a pral koresponn ak deziyasyon an "pi piti nimewo a pou katreven lèt pa ase", ki gen sèlman 78 lèt! Sou yon bò, nimewo sa a dwe egziste; an lòt men an, si nimewo sa a egziste, Lè sa a, deziyasyon li pa koresponn ak li. Paradoks!
Fason ki pi fasil pou ranvwaye paradoks sa a se fè referans ak enfòmalite notasyon vèbal yo. Tankou, si sèlman yon seri ekspresyon espesifikman defini yo te pèmèt nan notasyon an, lè sa a "pi piti nimewo a pou katreven lèt pa ase" pa ta yon notasyon valab, tandiske notasyon pratikman itil tankou "faktè nan uit" ta rete akseptab.
Èske gen fason fòmèl pou dekri sekans (algorithm) aksyon sou nimewo yo? Genyen, ak nan abondans - yo rele yo lang pwogramasyon. Olye de notasyon vèbal yo, nou pral sèvi ak pwogram (pa egzanp, nan Python) ki montre nimewo yo mande yo. Pou egzanp, pou senk nèf pwogram nan se apwopriye print("9"*5). Nou pral kontinye enterese nan pwogram ki pi kout la pou yon nimewo bay yo. Yo rele longè yon pwogram konsa nimewo; li se limit teyorik kote yon nimewo bay yo ka konprese.
Olye de paradoks Berry a, kounye a nou ka konsidere yon menm jan an: Ki pi piti nimewo ke yon pwogram kilookte pa ase pou pwodiksyon an?
Nou pral rezone menm jan ak anvan: gen 2561024 tèks kilobyte, ki vle di ke pa gen plis pase 2561024 nimewo kilookte pwogram yo ka soti. Sa vle di ke yon sèten nimewo ki pa pi gran pase 2561024 pa ka sòti nan fason sa a.
Men, ann ekri yon pwogram nan Python ki jenere tout tèks kilobyte posib, kouri yo pou ekzekisyon, epi si yo bay yon nimewo, Lè sa a, ajoute nimewo sa a nan diksyonè a nan sa yo ki ka jwenn. Apre w fin tcheke tout 2561024 posiblite yo, kèlkeswa tan li pran, pwogram nan chèche pi piti nimewo ki manke nan diksyonè a epi enprime nimewo sa a. Li sanble evidan ke yon pwogram konsa pral anfòm nan yon kilobyte nan kòd - epi li pral bay nimewo a menm ki pa ka soti nan yon pwogram kilobyte!
Ki sa ki trape an kounye a? Li pa ka atribiye ankò nan enfòmalite a nan notasyon an!
Si w konfonn pa lefèt ke pwogram nou an pral mande pou yon kantite astwonomik memwa travay - yon diksyonè (oswa ti etalaj) nan 2561024 eleman - Lè sa a, ou ka fè menm bagay la san li: pou chak nan 2561024 nimewo yo, nan vire. , ale nan tout 2561024 pwogram posib, jiskaske pa gen youn ki apwopriye. Li pa enpòtan ke rechèch sa a pral dire yon tan trè long: apre yo fin tcheke mwens pase (2561024) 2 pè soti nan nimewo a ak pwogram nan, li pral fini ak jwenn nimewo sa a anpil cheri.
Oswa li pap fini? Vreman vre, nan mitan tout pwogram ki pral eseye, pral genyen while True: pass (ak analogue fonksyonèl li yo) - ak pwoblèm nan pa pral pi lwen pase tès yon pwogram konsa!
Kontrèman ak paradoks Berry a, kote trape an te nan enfòmalite notasyon an, nan dezyèm ka a nou gen yon reformulasyon byen degize. . Reyalite a se ke li enposib detèmine pwodiksyon li nan yon pwogram nan yon tan fini. An patikilye, Kolmogorov konpleksite : pa gen okenn algorithm ki ta pèmèt, pou yon nimewo bay, jwenn longè pwogram ki pi kout ki enprime nimewo sa a; ki vle di pa gen solisyon pou pwoblèm Berry a - pou jwenn longè deziyasyon vèbal ki pi kout la pou yon nimewo bay yo.
Sous: www.habr.com