It probleem fan gegevenskompresje, yn syn ienfâldichste foarm, kin relatearje oan nûmers en har notaasjes. Sifers kinne wurde oanjûn troch sifers ("alve" foar it nûmer 11), wiskundige útdrukkingen ("twa yn 'e tweintichste" foar 1048576), tekenrige útdrukkingen ("fiif njoggenen" foar 99999), eigennammen ("nûmer fan it bist" foar 666, "jier fan 'e dea fan Turing" foar 1954), of willekeurige kombinaasjes dêrfan. Elke oantsjutting is geskikt dêr't de petearpartner kin dúdlik bepale hokker nûmer wy it oer. Fansels, fertel jo petearpartner "Faktoar fan acht" effisjinter as lykweardige notaasje "fjirtich tûzen trijehûndert en tweintich". In logyske fraach ûntstiet hjir: wat is de koartste notaasje foar in opjûn getal?
De filosoof Bertrand Russell publisearre yn 1908 , dy't de kwestje fan nûmernotaasje oanrekket fan 'e tsjinoerstelde kant: Wat is it lytste nûmer dat gjin tachtich letters fereasket?
Sa'n nûmer moat bestean: út tachtich Russyske letters en spaasjes kinne jo mar 3480 oantsjuttings meitsje, dat betsjut dat jo mei tachtich letters net mear as 3480 sifers oanwize kinne. Dit betsjut dat it ûnmooglik is om op dizze manier in bepaald oantal net mear as 3480 oan te jaan.
Dit betsjut dat dit nûmer oerienkomt mei de oantsjutting "it lytste nûmer dêr't tachtich letters net genôch foar binne", dat hat mar 78 letters! Oan de iene kant moat dit nûmer bestean; oan 'e oare kant, as dit nûmer bestiet, dan komt syn oantsjutting dêr net oer. Paradoks!
De maklikste manier om dizze paradoks te ûntslaan is te ferwizen nei de ynformaliteit fan verbale notaasjes. Lykas, as allinich in spesifyk definieare set fan útdrukkingen tastien is yn 'e notaasje, dan "it lytste nûmer dêr't tachtich letters net genôch foar binne" soe gjin jildige notaasje wêze, wylst praktysk nuttige notaasjes lykas "Faktoar fan acht" akseptabel bliuwe soe.
Binne der formele manieren om de folchoarder (algoritme) fan aksjes op nûmers te beskriuwen? D'r binne, en yn oerfloed - se wurde programmeartalen neamd. Ynstee fan verbale notaasjes sille wy programma's brûke (bygelyks yn Python) dy't de fereaske nûmers werjaan. Bygelyks foar fiif njoggenen is it programma geskikt print("9"*5). Wy sille fierder in v're ynteressearre yn de koartste programma foar in opjûn getal. De lingte fan sa'n programma hjit numbers; it is de teoretyske limyt dêr't in opjûn getal kin wurde komprimearre.
Ynstee fan Berry's paradoks kinne wy no in ferlykbere beskôgje: Wat is it lytste oantal dat in kilobyteprogramma net genôch is om út te fieren?
Wy sille op deselde wize redenearje as earder: der binne 2561024 kilobyte teksten, wat betsjut dat der net mear as 2561024 nûmers útjûn wurde kinne troch kilobyte programma's. Dit betsjut dat in bepaald oantal net grutter as 2561024 op dizze manier net ôflaat wurde kin.
Mar litte wy in programma yn Python skriuwe dat alle mooglike kilobyteteksten genereart, se útfiert foar útfiering, en as se in nûmer útfiere, dan foeget dit nûmer ta oan it wurdboek fan berikbere. Nei it kontrolearjen fan alle 2561024 mooglikheden, hoe lang it ek duorret, siket it programma nei it lytste nûmer dat mist yn it wurdboek en printet dat nûmer. It liket fanselssprekkend dat sa'n programma past yn in kilobyte koade - en sil it eigen getal útfiere dat net troch in kilobyte programma kin wurde útfierd!
Wat is it fangen no? It kin net mear taskreaun wurde oan de ynformaliteit fan de notaasje!
As jo yn 'e war binne troch it feit dat ús programma in astronomyske hoemannichte ûnthâld fereasket om te wurkjen - in wurdboek (of bitarray) fan 2561024 eleminten - dan kinne jo itselde ding dwaan sûnder dat: foar elk fan 'e 2561024 nûmers, op syn beurt , gean troch alle 2561024 mooglike programma's, oant der gjin geskikt is. It makket neat út dat sa'n sykjen in hiel lang duorret: nei it kontrolearjen fan minder as (2561024)2 pearen fan it nûmer en it programma, sil it einigje en dat tige koestere nûmer fine.
Of sil it net einigje? Ja, ûnder alle programma's dy't sille wurde besocht, sil d'r wêze while True: pass (en syn funksjonele analogen) - en de saak sil net fierder gean as it testen fan sa'n programma!
Oars as Berry syn paradoks, dêr't it fangen wie yn 'e ynformaliteit fan' e notaasje, yn it twadde gefal hawwe wy in goed fermomme herfoarming . It feit is dat it ûnmooglik is om syn útfier fan in programma yn in einige tiid te bepalen. Benammen Kolmogorov kompleksiteit : der is gjin algoritme dat soe tastean, foar in opjûn getal, te finen de lingte fan it koartste programma dat printsje dit nûmer; wat betsjut dat d'r gjin oplossing is foar Berry's probleem - om de lingte fan 'e koartste verbale oantsjutting foar in opjûn nûmer te finen.
Boarne: www.habr.com