Vandamálið við gagnaþjöppun, í sinni einföldustu mynd, getur tengst tölum og merkingum þeirra. Hægt er að tákna tölur með tölustöfum ("ellefu" fyrir töluna 11), stærðfræðiorð ("tveir á tuttugasta" fyrir 1048576), strengjatjáningar ("fimm níu" fyrir 99999), sérnöfn ("númer dýrsins" fyrir 666,- „dánarár Turing“ fyrir 1954), eða handahófskenndar samsetningar þeirra. Sérhver tilnefning er hentug þar sem viðmælandi getur greinilega ákvarðað hvaða tölu við erum að tala um. Segðu viðmælanda þínum það greinilega "þáttur af átta" skilvirkari en samsvarandi nótnaskrift „fjörutíu þúsund og þrjúhundrað og tuttugu“. Rökrétt spurning vaknar hér: hver er stysta merkingin fyrir tiltekna tölu?
Heimspekingurinn Bertrand Russell gaf út árið 1908 , sem snertir tölublaðið frá gagnstæðri hlið: Hver er minnsta talan sem þarf ekki áttatíu bókstafi?
Slík tala verður að vera til: úr áttatíu rússneskum stöfum og bilum er aðeins hægt að búa til 3480 tilnefningar, sem þýðir að með því að nota áttatíu stafi geturðu ekki tilgreint fleiri en 3480 tölustafi. Þetta þýðir að það er ómögulegt að tilgreina ákveðna tölu ekki meira en 3480 á þennan hátt.
Þetta þýðir að þessi tala mun samsvara tilnefningunni „minnsta talan sem áttatíu stafir duga ekki fyrir“, sem hefur aðeins 78 stafi! Annars vegar hlýtur þessi tala að vera til; á hinn bóginn, ef þessi tala er til, þá samsvarar tilnefning hennar ekki henni. Þversögn!
Auðveldasta leiðin til að hafna þessari þversögn er að vísa til óformlegs orðamerkja. Eins og, ef aðeins sérstaklega skilgreint sett af tjáningum væri leyft í nótnaskriftinni, þá „minnsta talan sem áttatíu stafir duga ekki fyrir“ væri ekki gild nótnaskrift, en hagnýtar nótur eins og "þáttur af átta" yrði áfram ásættanlegt.
Eru til formlegar leiðir til að lýsa röð (algrími) aðgerða á tölum? Það eru til, og í gnægð - þau eru kölluð forritunarmál. Í stað munnlegra merkinga munum við nota forrit (til dæmis í Python) sem sýna nauðsynlegar tölur. Til dæmis, fyrir fimm níu, forritið hentar print("9"*5). Við munum halda áfram að hafa áhuga á stysta prógramminu fyrir tiltekið númer. Lengd slíks forrits er kallað tölur; það er fræðileg takmörk sem hægt er að þjappa tiltekinni tölu að.
Í stað þverstæðu Berrys getum við nú íhugað svipaða: Hver er minnsta talan sem kílóbætaforrit dugar ekki til að gefa út?
Við munum rökræða á sama hátt og áður: það eru 2561024 kílóbæti textar, sem þýðir að ekki er hægt að gefa út fleiri en 2561024 tölur með kílóbæta forritum. Þetta þýðir að ekki er hægt að fá ákveðna tölu sem er ekki hærri en 2561024 á þennan hátt.
En við skulum skrifa forrit í Python sem býr til alla mögulega kílóbæta texta, keyrir þá til framkvæmdar og ef þeir gefa út tölu, bætir þá þessari tölu við orðabókina yfir þá sem hægt er að ná í. Eftir að hafa skoðað alla 2561024 möguleikana, sama hversu langan tíma það tekur, leitar forritið að minnsta númerinu sem vantar í orðabókina og prentar það númer. Það virðist augljóst að slíkt forrit passar inn í kílóbæti af kóða - og mun gefa út þann fjölda sem kílóbæta forrit getur ekki gefið út!
Hver er gripurinn núna? Það er ekki lengur hægt að rekja það til óformlegs ritunar!
Ef þú ert ruglaður af þeirri staðreynd að forritið okkar mun krefjast stjarnfræðilegs magns af minni til að virka - orðabók (eða bitafylki) með 2561024 þáttum - þá geturðu gert það sama án þess: fyrir hverja af 2561024 tölunum, aftur á móti , farðu í gegnum öll 2561024 möguleg forrit, þar til enginn hentugur er til. Það skiptir ekki máli að slík leit endist mjög lengi: eftir að hafa athugað minna en (2561024)2 pör úr númerinu og forritinu lýkur hún og finnur þessa mjög dýrmætu tölu.
Eða mun það ekki klárast? Reyndar, meðal allra forritanna sem verða prófuð, verður það while True: pass (og hagnýtar hliðstæður þess) - og málið mun ekki ganga lengra en að prófa slíkt forrit!
Ólíkt þversögn Berrys, þar sem gripurinn var í óformleika nótnaskriftarinnar, í öðru tilvikinu höfum við vel dulbúna umbreytingu . Staðreyndin er sú að það er ómögulegt að ákvarða úttak þess úr forriti á endanlegum tíma. Einkum Kolmogorov flókið : það er ekkert reiknirit sem myndi leyfa, fyrir tiltekna tölu, að finna lengd stysta forritsins sem prentar þessa tölu; sem þýðir að það er engin lausn á vandamáli Berrys - að finna lengdina á stystu munnlegu merkingunni fyrir tiltekna tölu.
Heimild: www.habr.com