Qhov teeb meem ntawm cov ntaub ntawv compression, hauv nws daim ntawv yooj yim tshaj plaws, tuaj yeem cuam tshuam rau cov lej thiab lawv cov cim. Cov lej tuaj yeem txhais tau los ntawm cov lej (" kaum ib" rau tus naj npawb 11), kev qhia lej ("ob nyob rau hauv nees nkaum" rau 1048576), kab lus ("tsib cuaj" rau 99999), cov npe tsim nyog ("tus naj npawb ntawm cov tsiaj nyaum" rau 666,. "xyoo ntawm Turing tuag" rau xyoo 1954), los yog kev sib koom ua ke ntawm nws. Ib qho kev xaiv tsim nyog los ntawm qhov uas tus interlocutor tuaj yeem txiav txim siab seb tus lej twg peb tab tom tham txog. Obviously, qhia rau koj tus interlocutor "factorial ntawm yim" muaj txiaj ntsig ntau dua li qhov sib npaug " plaub caug txhiab peb puas nees nkaum". Cov lus nug uas muaj tseeb tshwm sim ntawm no: Dab tsi yog qhov luv tshaj plaws rau tus lej muab?
Tus kws tshawb fawb Bertrand Russell tau luam tawm xyoo 1908 , uas kov ntawm qhov teeb meem ntawm tus lej cim los ntawm sab nraud: Tus lej tsawg tshaj plaws uas tsis xav tau yim caum tsab ntawv yog dab tsi?
Xws li tus lej yuav tsum muaj nyob: los ntawm yim caum tus tsiaj ntawv Lavxias thiab qhov chaw koj tuaj yeem tsim tau tsuas yog 3480 tus qauv, uas txhais tau hais tias siv yim caum tsab ntawv koj tuaj yeem xaiv tsis ntau tshaj 3480 tus lej. Qhov no txhais tau hais tias nws tsis tuaj yeem xaiv tus lej tsis muaj ntau tshaj 3480 hauv txoj kev no.
Qhov no txhais tau hais tias tus lej no yuav raug rau qhov kev xaiv "tus lej tsawg tshaj plaws uas yim caum tsab ntawv tsis txaus", uas tsuas muaj 78 tsab ntawv! Ntawm ib sab, tus lej no yuav tsum muaj nyob; ntawm qhov tod tes, yog tias tus lej no muaj, ces nws lub npe tsis sib haum rau nws. Paradox!
Txoj hauv kev yooj yim tshaj plaws los tso tseg qhov kev tsis sib haum xeeb no yog xa mus rau qhov tsis raug cai ntawm cov lus hais. Zoo li, yog tias tsuas yog ib qho tshwj xeeb ntawm cov kab lus tau tso cai rau hauv cov ntawv sau, ces "tus lej tsawg tshaj plaws uas yim caum tsab ntawv tsis txaus" yuav tsis yog ib tug siv tau notation, whereas siv tau zoo notations nyiam "factorial ntawm yim" yuav nyob tau.
Puas muaj txoj hauv kev los piav qhia cov kab ke (algorithm) ntawm kev ua ntawm tus lej? Muaj, thiab nyob rau hauv abundance - lawv hu ua programming lus. Hloov ntawm cov lus hais, peb yuav siv cov kev pab cuam (piv txwv li, hauv Python) uas tso saib cov lej xav tau. Piv txwv li, rau tsib cuaj qhov kev pab cuam yog tsim nyog print("9"*5). Peb tseem yuav txaus siab rau qhov kev pabcuam luv tshaj plaws rau tus lej muab. Qhov ntev ntawm qhov kev pab cuam no hu ua tus lej; nws yog qhov kev txwv theoretical uas tus lej muab tau tuaj yeem raug compressed.
Hloov ntawm Berry's paradox, tam sim no peb tuaj yeem xav txog qhov zoo sib xws: Dab tsi yog tus lej tsawg tshaj plaws uas qhov kev pab cuam kilobyte tsis txaus tso tawm?
Peb yuav laj laj nyob ib yam li ua ntej: muaj 2561024 kilobyte cov ntawv, uas txhais tau hais tias tsis muaj ntau tshaj 2561024 tus lej tuaj yeem tso tawm los ntawm cov kev pabcuam kilobyte. Qhov no txhais tau hais tias qee tus lej tsis muaj ntau dua 2561024 tsis tuaj yeem muab los ntawm txoj kev no.
Tab sis cia peb sau ib qho kev pab cuam hauv Python uas tsim tag nrho cov ntawv nyeem tau kilobyte, khiav lawv rau kev ua tiav, thiab yog tias lawv tso tawm tus lej, tom qab ntawd ntxiv tus lej no rau phau ntawv txhais lus ntawm cov tuaj yeem ncav cuag. Tom qab kuaj xyuas tag nrho 2561024 qhov muaj peev xwm, txawm tias nws yuav siv sijhawm ntev npaum li cas, qhov kev zov me nyuam nrhiav tus lej tsawg tshaj plaws uas ploj lawm ntawm phau ntawv txhais lus thiab luam tawm tus lej ntawd. Nws zoo nkaus li pom tseeb tias qhov kev zov me nyuam yuav haum rau hauv ib kilobyte ntawm code - thiab yuav tso tawm tus lej uas tsis tuaj yeem tso tawm los ntawm qhov kev pab cuam kilobyte!
Dab tsi yog qhov ntes tam sim no? Nws tsis tuaj yeem raug ntaus nqi rau qhov tsis raug ntawm cov ntawv sau!
Yog tias koj tsis meej pem los ntawm qhov tseeb tias peb qhov kev zov me nyuam yuav xav tau ib qho astronomical ntawm lub cim xeeb ua haujlwm - phau ntawv txhais lus (los yog me ntsis array) ntawm 2561024 ntsiab - ces koj tuaj yeem ua tib yam yam tsis muaj nws: rau txhua tus ntawm 2561024 tus lej, nyob rau hauv lem , mus dhau tag nrho 2561024 cov kev pab cuam, kom txog rau thaum tsis muaj qhov tsim nyog. Nws tsis muaj teeb meem tias qhov kev tshawb fawb zoo li no yuav kav ntev heev: tom qab kuaj xyuas tsawg dua (2561024) 2 khub ntawm tus lej thiab qhov kev zov me nyuam, nws yuav xaus thiab pom tus lej uas nyiam heev.
Los yog nws yuav tsis tiav? Tseeb, ntawm tag nrho cov kev pab cuam uas yuav tau sim, yuav muaj while True: pass (thiab nws cov kev ua haujlwm analogues) - thiab qhov teeb meem yuav tsis mus ntxiv dua li kev sim cov kev pab cuam!
Tsis zoo li Berry's paradox, qhov twg qhov ntes tau nyob rau hauv qhov tsis raug ntawm cov ntawv sau tseg, hauv qhov thib ob peb muaj kev hloov kho kom zoo. . Qhov tseeb yog tias nws tsis tuaj yeem txiav txim siab nws cov txiaj ntsig los ntawm qhov kev zov me nyuam nyob rau lub sijhawm kawg. Hauv particular, Kolmogorov complexity : tsis muaj algorithm uas yuav tso cai, rau tus lej muab, nrhiav qhov ntev ntawm qhov kev pab cuam luv tshaj plaws uas luam tawm tus lej no; uas txhais tau hais tias tsis muaj kev daws teeb meem rau Berry qhov teeb meem - nrhiav qhov ntev ntawm cov lus luv tshaj plaws rau tus lej muab.
Tau qhov twg los: www.hab.com