Az adattömörítés problémája a legegyszerűbb formájában a számokhoz és jelöléseikhez köthető. A számokat számokkal jelölhetjük ("tizenegy" a 11-es szám esetén matematikai kifejezések ("kettő a huszadikban" 1048576 esetén), karakterlánc kifejezések ("öt kilences" a 99999-hez), tulajdonnevek ("a fenevad száma" 666-ért, "Turing halálának éve" 1954-re), vagy ezek tetszőleges kombinációi. Bármely megjelölés alkalmas arra, hogy a beszélgetőpartner egyértelműen meghatározza, melyik számról beszélünk. Nyilvánvalóan szóljon a beszélgetőpartnerének "nyolc faktor" hatékonyabb, mint az egyenértékű jelölés "negyvenezer-háromszázhúsz". Felmerül itt egy logikus kérdés: mi a legrövidebb jelölés egy adott számhoz?
Bertrand Russell filozófus 1908-ban publikált , amely az ellenkező oldalról érinti a számok jelölésének kérdését: Mi az a legkisebb szám, amelyhez nem kell nyolcvan betű?
Egy ilyen számnak léteznie kell: nyolcvan orosz betűből és szóközből csak 3480 jelölést tehet ki, ami azt jelenti, hogy nyolcvan betűvel legfeljebb 3480 számot jelölhet ki. Ez azt jelenti, hogy lehetetlen egy bizonyos számot 3480-nál nem többet ilyen módon kijelölni.
Ez azt jelenti, hogy ez a szám megfelel a megnevezésnek "a legkisebb szám, amelyhez nem elég nyolcvan betű", aminek csak 78 betűje van! Egyrészt ennek a számnak léteznie kell; másrészt, ha ez a szám létezik, akkor a megnevezése nem felel meg annak. Paradoxon!
Ezt a paradoxont a legkönnyebben a verbális jelölések informalitására hivatkozva lehet elvetni. Mint ha csak egy konkrétan meghatározott kifejezéshalmaz lenne megengedett a jelölésben, akkor "a legkisebb szám, amelyhez nem elég nyolcvan betű" nem lenne érvényes jelölés, míg a gyakorlatilag hasznos jelölések pl "nyolc faktor" elfogadható maradna.
Vannak formális módszerek a számokon végrehajtott műveletek sorozatának (algoritmusának) leírására? Vannak, és bőségesen - programozási nyelveknek nevezik. A szóbeli jelölések helyett olyan programokat fogunk használni (például Pythonban), amelyek megjelenítik a szükséges számokat. Például öt kilencre megfelelő a program print("9"*5). Továbbra is érdeklődni fogunk egy adott szám legrövidebb programja iránt. Egy ilyen program hosszát ún számok; ez az elméleti határ, ameddig egy adott szám tömöríthető.
Berry paradoxona helyett most egy hasonlót is fontolóra vehetünk: Mi az a legkisebb szám, amelynek kiadásához egy kilobájtos program nem elég?
Ugyanúgy érvelünk, mint korábban: 2561024 kilobájtos szöveg van, ami azt jelenti, hogy a kilobyte-os programok legfeljebb 2561024 számot adhatnak ki. Ez azt jelenti, hogy 2561024-nél nem nagyobb szám nem származtatható így.
De írjunk Pythonban egy programot, amely az összes lehetséges kilobájtos szöveget legenerálja, lefuttatja azokat végrehajtásra, és ha számot ad ki, akkor hozzáadja ezt a számot az elérhetők szótárához. Mind a 2561024 XNUMX XNUMX lehetőség ellenőrzése után, függetlenül attól, hogy mennyi ideig tart, a program megkeresi a szótárból hiányzó legkisebb számot, és kiírja azt. Kézenfekvőnek tűnik, hogy egy ilyen program belefér egy kilobájt kódba - és pontosan azt a számot adja ki, amelyet egy kilobájtos program nem tud kiadni!
Most mi a fogás? Már nem a jelölés informalitásának tudható be!
Ha megzavarja, hogy programunknak csillagászati mennyiségű memóriára lesz szüksége a működéséhez - egy szótárra (vagy bittömbre) 2561024 elemből -, akkor enélkül is megteheti ugyanezt: a 2561024 számok mindegyikéhez viszont , menjen végig mind a 2561024 lehetséges programon, amíg nem lesz megfelelő. Nem számít, hogy egy ilyen keresés nagyon sokáig tart: miután a számból és a programból kevesebb mint (2561024)2 párost ellenőriz, leáll, és megtalálja azt a nagyon dédelgetett számot.
Vagy nem lesz vége? Valóban, az összes kipróbálható program között lesz while True: pass (és funkcionális analógjai) - és a dolog nem megy tovább egy ilyen program tesztelésénél!
Ellentétben Berry paradoxonával, ahol a fogás a jelölés informalitásában volt, a második esetben egy jól álcázott újrafogalmazásunk van. . A tény az, hogy lehetetlen meghatározni a kimenetét egy programból véges idő alatt. Különösen a Kolmogorov-komplexitás : nincs olyan algoritmus, amely egy adott szám esetén lehetővé tenné, hogy megtalálja a legrövidebb program hosszát, amely ezt a számot írja ki; ami azt jelenti, hogy nincs megoldás Berry problémájára – meg kell találni egy adott szám legrövidebb szóbeli megnevezésének hosszát.
Forrás: will.com