Datuen konpresioaren arazoa, bere forma sinpleenean, zenbakiekin eta haien notazioekin erlazionatu daiteke. Zenbakiak zenbaki bidez adieraz daitezke ("hamaika" 11 zenbakirako), adierazpen matematikoak ("bi XX.ean" 1048576rako), kate-adierazpenak ("bost bederatzi" 99999rako), izen propioak ("piztiaren kopurua" 666rako, "Turingen heriotzaren urtea" 1954rako), edo horien konbinazio arbitrarioak. Edozein izendapen egokia da solaskideak zein zenbakitaz ari garen argi eta garbi zehazteko. Jakina, esan zure solaskideari "zortziren faktorea" notazio baliokidea baino eraginkorragoa "berrogei mila hirurehun hogei". Galdera logiko bat sortzen da hemen: zein da zenbaki jakin baterako notaziorik laburrena?
Bertrand Russell filosofoak 1908an argitaratu zuen , zenbaki-notazioaren gaia kontrako aldetik ukitzen duena: Zein da laurogei hizki behar ez dituen zenbakirik txikiena?
Halako zenbaki batek egon behar du: laurogei hizki eta zuriune errusiaretatik 3480 izendapen baino ezin dituzu egin, hau da, laurogei letra erabiliz ezin dituzu 3480 zenbaki baino gehiago izendatu. Horrek esan nahi du ezinezkoa dela modu honetan 3480 baino gehiago kopuru jakin bat izendatzea.
Horrek esan nahi du zenbaki hori izendapenarekin bat etorriko dela "laurogei letra nahikoa ez den zenbakirik txikiena", 78 letra baino ez dituena! Alde batetik, kopuru hori egon behar da; aldiz, zenbaki hori existitzen bada, bere izendapena ez dagokio. Paradoxa!
Paradoxa hori baztertzeko modurik errazena hitzezko notazioen informaltasuna aipatzea da. Esaterako, idazkeran berariaz definitutako esamolde multzo bat bakarrik onartzen balitz, orduan "laurogei letra nahikoa ez den zenbakirik txikiena" ez litzateke baliozko notazio bat izango, eta ia erabilgarria bezalako notazioek "zortziren faktorea" onargarria izango litzateke.
Ba al dago zenbakien ekintzen segida (algoritmoa) deskribatzeko modu formalik? Badira, eta ugariak, programazio-lengoaiak deitzen zaie. Hitzezko notazioen ordez, eskatutako zenbakiak bistaratzen dituzten programak erabiliko ditugu (adibidez, Python-en). Adibidez, bost bederatzirako programa egokia da print("9"*5). Zenbaki jakin baterako programarik laburrena interesatzen jarraituko dugu. Programa horren luzera deitzen da zenbakiak; zenbaki jakin bat konprimitu daitekeen muga teorikoa da.
Berryren paradoxaren ordez, orain antzeko bat kontsidera dezakegu: Zein da kilobyte-ko programa batek ateratzeko nahikoa ez den kopururik txikiena?
Lehengo modu berean arrazoituko dugu: 2561024 kilobyte-ko testuak daude, hau da, 2561024 zenbaki baino gehiago ezin dira atera kilobyte-ko programek. Horrek esan nahi du 2561024 baino handiagoa ez den kopuru jakin bat ezin dela era honetan eratorri.
Baina idatz dezagun programa bat Python-en, kilobyte-testu posible guztiak sortzen dituena, exekutatzeko exekutatzen dituena eta zenbaki bat ateratzen badute, zenbaki hori eskura daitezkeen hiztegira gehitzen du. 2561024 aukera guztiak egiaztatu ondoren, zenbat denbora behar duen, programak hiztegian falta den zenbakirik txikiena bilatzen du eta zenbaki hori inprimatzen du. Bistan da programa hori kilobyte kode batean sartuko dela, eta kilobyte-ko programa batek atera ezin duen zenbakia aterako duela!
Zein da orain harrapaketa? Jada ezin zaio notazio informalari egotzi!
Nahastuta bazaude gure programak memoria kopuru astronomiko bat behar duela funtzionatzeko - 2561024 elementuko hiztegia (edo bit-matrizea) - orduan gauza bera egin dezakezu hori gabe: 2561024 zenbaki bakoitzeko, txandaka. , joan 2561024 programa posible guztiak, egokirik ez dagoen arte. Ez du axola horrelako bilaketak denbora luzez iraungo duenik: zenbakitik eta programatik (2561024)2 bikote baino gutxiago egiaztatu ondoren, amaitu eta oso kuttun dagoen zenbaki hori aurkituko du.
Edo ez da amaituko? Izan ere, probatuko diren programa guztien artean, egongo dira while True: pass (eta bere analogo funtzionalak) - eta kontua ez da horrelako programa bat probatzea baino harago joango!
Berryren paradoxa ez bezala, non harrapaketa notazio informalean zegoen, bigarren kasuan ondo mozorrotutako birformulazioa dugu. . Izan ere, ezinezkoa dela programa batetik ateratzea denbora finitu batean zehaztea. Bereziki, Kolmogorov konplexutasuna : ez dago zenbaki jakin baterako zenbaki hori inprimatzen duen programa laburrenaren luzera aurkitzea ahalbidetuko lukeen algoritmorik; horrek esan nahi du ez dagoela Berry-ren arazoari irtenbiderik - zenbaki jakin baterako hitzezko izendapen laburrenaren luzera aurkitzea.
Iturria: www.habr.com