Die probleem van datakompressie, in sy eenvoudigste vorm, kan verband hou met getalle en hul notasies. Getalle kan deur syfers aangedui word ("elf" vir die getal 11), wiskundige uitdrukkings ("twee in die twintigste" vir 1048576), string uitdrukkings ("vyf nege" vir 99999), eiename ("nommer van die dier" vir 666, "jaar van Turing se dood" vir 1954), of arbitrêre kombinasies daarvan. Enige benaming is geskik waarmee die gespreksgenoot duidelik kan bepaal van watter getal ons praat. Vertel natuurlik jou gespreksgenoot "faktor van agt" meer doeltreffend as ekwivalente notasie "veertigduisend driehonderd twintig". 'n Logiese vraag ontstaan hier: wat is die kortste notasie vir 'n gegewe getal?
Die filosoof Bertrand Russell het in 1908 gepubliseer , wat die kwessie van getalnotasie van die teenoorgestelde kant aanraak: Wat is die kleinste getal wat nie tagtig letters benodig nie?
So 'n nommer moet bestaan: uit tagtig Russiese letters en spasies kan jy slegs 3480 benamings opmaak, wat beteken dat jy met tagtig letters nie meer as 3480 nommers kan aanwys nie. Dit beteken dat dit onmoontlik is om 'n sekere getal nie meer as 3480 op hierdie manier aan te dui nie.
Dit beteken dat hierdie nommer met die benaming sal ooreenstem "die kleinste getal waarvoor tagtig letters nie genoeg is nie", wat slegs 78 letters het! Aan die een kant moet hierdie nommer bestaan; aan die ander kant, as hierdie getal bestaan, dan stem sy benaming nie daarmee ooreen nie. Paradoks!
Die maklikste manier om hierdie paradoks te verwerp, is om na die informaliteit van verbale notasies te verwys. Soos, as slegs 'n spesifiek gedefinieerde stel uitdrukkings in die notasie toegelaat word, dan "die kleinste getal waarvoor tagtig letters nie genoeg is nie" sou nie 'n geldige notasie wees nie, terwyl prakties bruikbare notasies soos "faktor van agt" aanvaarbaar sou bly.
Is daar formele maniere om die volgorde (algoritme) van aksies op getalle te beskryf? Daar is, en in oorvloed - dit word programmeertale genoem. In plaas van verbale notasies, sal ons programme gebruik (byvoorbeeld in Python) wat die vereiste getalle vertoon. Byvoorbeeld, vir vyf nege is die program geskik print("9"*5). Ons sal steeds belangstel in die kortste program vir 'n gegewe nommer. Die lengte van so 'n program word genoem getalle; dit is die teoretiese limiet waartoe 'n gegewe getal saamgepers kan word.
In plaas van Berry se paradoks, kan ons nou 'n soortgelyke een oorweeg: Wat is die kleinste getal wat 'n kilogreepprogram nie genoeg is om uit te voer nie?
Ons sal op dieselfde manier as voorheen redeneer: daar is 2561024 kilogrepe-tekste, wat beteken dat nie meer as 2561024 getalle deur kilogrepe-programme uitgevoer kan word nie. Dit beteken dat 'n sekere getal nie groter as 2561024 nie op hierdie manier afgelei kan word nie.
Maar kom ons skryf 'n program in Python wat alle moontlike kilogrepe-tekste genereer, dit laat loop vir uitvoering, en as hulle 'n nommer uitvoer, voeg dan hierdie nommer by die woordeboek van bereikbares. Nadat al 2561024 XNUMX XNUMX moontlikhede nagegaan is, maak nie saak hoe lank dit neem nie, die program soek die kleinste getal wat in die woordeboek ontbreek en druk daardie nommer. Dit lyk voor die hand liggend dat so 'n program in 'n kilogreep kode sal inpas - en die getal sal uitstuur wat nie deur 'n kilogreepprogram uitgevoer kan word nie!
Wat is die vangs nou? Dit kan nie meer toegeskryf word aan die informaliteit van die notasie nie!
As jy verwar word deur die feit dat ons program 'n astronomiese hoeveelheid geheue sal benodig om te werk - 'n woordeboek (of bietjie-skikking) van 2561024 elemente - dan kan jy dieselfde ding daarsonder doen: vir elk van die 2561024 nommers, op sy beurt , gaan deur al 2561024 moontlike programme, totdat daar geen geskikte een is nie. Dit maak nie saak dat so 'n soektog baie lank sal duur nie: nadat jy minder as (2561024)2 pare van die nommer en die program nagegaan het, sal dit eindig en daardie baie gekoesterde nommer vind.
Of sal dit nie klaar wees nie? Inderdaad, onder al die programme wat beproef sal word, sal daar wees while True: pass (en sy funksionele analoë) - en die saak gaan nie verder as om so 'n program te toets nie!
Anders as Berry se paradoks, waar die vangplek in die informaliteit van die notasie was, het ons in die tweede geval 'n goed vermomde herformulering . Die feit is dat dit onmoontlik is om sy uitset van 'n program in 'n beperkte tyd te bepaal. In die besonder, Kolmogorov kompleksiteit : daar is geen algoritme wat dit vir 'n gegewe getal sal toelaat om die lengte van die kortste program te vind wat hierdie nommer druk nie; wat beteken daar is geen oplossing vir Berry se probleem nie - om die lengte van die kortste verbale benaming vir 'n gegewe getal te vind.
Bron: will.com