Az adatok tömörítésének feladata legegyszerűbb formájában a számokra és jelölésükre vonatkozhat. A számokat számmal lehet jelölni (tizenegy a 11-es szám számára), matematikai kifejezésekkel (kettő a huszadikon 1048576-ra), szöveges kifejezésekkel (öt kilences a 99999-re), tulajdonnevekkel (a fenevad száma a 666-ra, Turing halálának éve 1954-re), vagy bármilyen véletlenszerű kombinációjukkal. Bármilyen jelölés érvényes, amellyel a beszélgetőpartner egyértelműen meg tudja határozni, hogy melyik számról van szó. Nyilvánvaló, hogy elmondani a beszélgetőpartnernek a nyolc faktoriálisa hatékonyabb, mint az ekvivalens jelölés negyven ezer háromszázhúsz.Itt felmerül a logikus kérdés: mi a legrövidebb jelölés a megadott számra?
Bertrand Russell filozófus 1908-ban publikálta , amely a számok jelölésének kérdését a másik oldalról érinti: melyik a legkisebb szám, amely megjelöléséhez nem elegendő nyolcvan betű?
Olyan számnak kell léteznie: nyolcvan orosz betű és szóköz felhasználásával csak 3480 jelölést lehet létrehozni, tehát nyolcvan betű felhasználásával legfeljebb 3480 szám jelölhető. Ezért egy olyan szám, amely nem nagyobb mint 3480, így nem jelölhető.
Ezért ennek a számnak a jelölése a legkisebb szám, amely megjelöléséhez nem elegendő nyolcvan betű, amelyben mindössze 78 betű található! Egyrészt ennek a számnak léteznie kell; másrészt, ha ez a szám létezik, akkor a jelölése nem felel meg neki. Paradoxon!
A legegyszerűbb módja, hogy elhessegetjük ezt a paradoxont, ha a szóbeli jelölések informális voltára hivatkozunk. Mondván, ha csak konkrétan meghatározott kifejezések lennének megengedettek a jelölésekben, akkor a legkisebb szám, amely megjelöléséhez nem elegendő nyolcvan betű nem lenne elfogadható jelölés, míg a gyakorlatilag hasznos jelölések, mint a nyolc faktoriálisa maradnának elfogadhatóknak.
Vannak-e formális módszerek a számokkal kapcsolatos tevékenységek (algoritmusok) leírására? Igen, és bőségesen — őket programozási nyelveknek hívják. Helyettük a szóbeli jelöléseknek programokat használjunk (például Pythonban), amelyek a szükséges számokat kiadják. Például, az öt kilenseshez megfelelő lesz a program print("9"*5). Továbbra is érdekel minket a legrövidebb program a megadott számhoz. Az ilyen program hosszát nevezik; ez a elméleti határ, ameddig a megadott számot tömöríteni lehet.
A Berry-paradoxon helyett most hasonló lehetőséget vizsgálhatunk: mi a legkisebb szám, amelynek kiírásához nem elegendő egy kilobytes program?
A következő módon érvelünk, mint eddig: létezik 2561024 kilobájtos szöveg, tehát kilobájtos programokkal legfeljebb 2561024 számot lehet kiírni. Ezért van egy olyan szám, amelyet legfeljebb 2561024-tel ilyen módon nem lehet kiírni.
De írjunk egy Python programot, amely generálja az összes lehetséges kilobájt szöveget, futtatja őket, és ha valamelyik számot kiír, akkor ezt a számot hozzáadja a megvalósítható számok szótárához. Minden 2561024 lehetőség ellenőrzése után, bármennyi időt is vesz igénybe, a program keresi a legkisebb számot, amely hiányzik a szótárból, és ezt a számot kiírja. Nyilvánvalónak tűnik, hogy egy ilyen program belefér a kilobájtnyi kódba — és kiírja azt a számot, amelyet nem lehet kiírni kilobájt program segítségével!
De hol a csapda? A jelölések informálissága már nem írható rá!
Ha az zavarja, hogy a programunk óriási mennyiségű memóriát igényel a működéséhez — egy 2561024 elemű szótár (vagy bitminta) — akkor mindezt meg lehet valósítani nélküle is: minden 2561024 számot egyenként sorra kell venni, és kipróbálni az összes 2561024 lehetséges programot, amíg meg nem találjuk a megfelelőt. Nem számít, hogy ez a fajta keresés milyen hosszú ideig tart: a szám és a program párok kevesebb mint (2561024)2 ellenőrzése után a program befejeződik, és megtalálja azt az áhított számot.
Vagy mégsem? Hiszen a kipróbált programok között ott lesz while True: pass (és funkcionális analógjai) — és a program ellenőrzésének további része már nem folytatódik!
A Berry-paradoxonhoz képest, ahol a csapda a jelölések informálisságában rejlett, a második esetben jól álcázott átkonstruálása van a A lényeg az, hogy egy program kimenetét korlátozott idő alatt nem lehet meghatározni. Különösen a Kolmogorov-komplexitás : nincs olyan algoritmus, amely lehetővé tenné, hogy egy adott számhoz megtaláljuk a legközelebbi program hossza, ami ezt a számot produkálja; ezért a Berry-probléma megoldása is lehetetlen — egy adott számhoz találjuk meg a legrövidebb szóbelileg kifejezett hosszot.
Forrás: habr.com
