Lovász László

2. Információtartalom és véletlenség

Az elsőnek megadott sorozatot (3. ábra) azonban nem tudnám ilyen egyszerűen leírni, definiálni: igazában semmi más értelmes módon nem írható le, mint azzal, hogy felsoroljuk az elemeit. Pontosan ezzel definiálhatjuk a véletlen sorozatot: egy sorozat akkor véletlen, ha nem írható le rövidebben, mint a saját hossza.

Általánosabban megfogalmazva azt nevezzük egy sorozat vagy bármilyen más struktúra, kép stb. informaciótartalmának (vagy másnéven információs bonyolultságának), hogy milyen hosszú a lehető legrövidebb leírása, mennyire lehet tömöríteni a sorozatot a lehető leghatékonyabb kódolást használva. (Ez matematikailag pontosan definiálható.)

Ezek után véletlen az a sorozat, melynek az információtartalma a hosszánál nem lényegesen kisebb. Megmutatható, hogy az ilyen módon definiált véletlen sorozatokra a valószínűségszámítás alapvető eredményei, például a nagy számok törvényei érvényesek lesznek.

A 19-20. század fordulóján Hilbert, a nagy német matematikus megfogalmazta az akkori matematika legfontosabb megoldatlan problémáit. Ezek egyike a valószínűség fogalmának megalapozása volt. Először von Mises tett kísérletet arra, hogy ezt megoldja, olyasformán, ahogyan mi próbáltuk az előbb: egy fej-írás-sorozatot véletlennek nevezett, ha a sorozatban közel azonos a fejek és írások gyakorisága, és ez áll akkor is, ha csak minden második vagy minden harmadik elemet nézzük stb. Ez azonban nem vezetett sikerre.

9. ábra

3. Véletlen és álvéletlen

Van azonban a bonyolultság fogalmának egy hátránya is: egy sorozat bonyolultságát nem lehet semmilyen algoritmussal sem kiszámítani. Továbbá, ilyen értelemben véletlen számokat számítógéppel generálni fából vaskarika, hiszen egy számítógéppel generált sorozat információtartalma csak annyi, mint az őt generáló program információtartalma, ami a sorozat hosszától függetlenül korlátos.

Mivel azonban számítógép által generált véletlen számokra szükség van, egy más fogalommal kell dolgozni. A bonyolultságelmélet segítségével két új kritériumot kaphatunk arra a kérdésre, hogy mikor tekinthetünk egy sorozatot véletlennek.

1) Képzeljük el, hogy két gépünk van, melyek mindegyike 0-kat és 1-eseket nyomtat egy papírra. Az egyik gépben egy igazi véletlent előállító fizikai eszköz van, és a kiadott sorozat egymástól független bitekből áll, melyek 1 valószínűséggel lehetnek 0 vagy 1. A másik gépben egy program gyártja a számokat egy rövid "magból", azaz egy olyan számból, amely a generáló algoritmus kiinduló (inicializáló) értéke. A programot ismerjük, a magról azonban csak annyit tudunk, hogy hány jegyű. A legfontosabb: nem tudjuk, melyik gép melyik. A feladatunk, hogy ezt megtippeljük. (Előfordulhat, hogy a valódi véletlent adó gép véletlenül olyan sorozatot állít elő, melyet az álvéletlent adó gép is előállíthat. Ebben az esetben nem tudunk biztos választ adni. Ennek azonban igen kicsi a valószínűsége.)

Ha korlátlan idő állna rendelkezésre, akkor könnyű volna igen jó eséllyel tippelni: egyszerűen kipróbálnánk minden egyes magot, hogy abból indulva melyik generátor produkálja a megfigyelt sorozatot. Ehhez azonban 2ⁿ sorozatot kell kipróbálnunk. Így ezt a túl könnyű megoldást kizárhatjuk azzal, hogy csak polinomiális algoritmust engedünk meg.

Egy másik triviális, érdektelen megoldás az volna, ha úgy tippelnénk meg, hogy melyik sorozat az igazi véletlen, hogy feldobunk egy forintot. Az esetek felében ez jó eredmenyt ad. Ahhoz, hogy ezt kizárjuk, megköveteljük, hogy a felismerő algoritmus az esetek több mint felében adjon jó eredményt. Pontosabban azt követeljük meg, hogy annak a valószínűsége, hogy az algoritmus helyesen tippeli meg, hogy melyik sorozat a véletlen, legalább 51% legyen.

Akkor mondjuk tehát, hogy a generátor az igazitól megkülönböztethetetlen, ha nincs olyan algoritmus, mely polinomiális időben az esetek 51%-ában helyesen tippeli meg, hogy melyik gép az, amelyik a valódi véletlen sorozatot adja.

2) Képzeljük el, hogy csak egy gépünk van, melyről tudjuk, hogy álvéletlen-sorozatot állít elő, ismert programmal, de a magról ismét csak azt tudjuk, hogy milyen hosszú. Megfigyeljük a kijövő sorozatot, de mielőtt egy-egy újabb jegyét megnéznénk, megpróbáljuk megtippelni, hogy mi lesz a következő. Az előzőekhez hasonlóan, a tippeléshez csak polinomiális időt használhatunk, és annyit kell elérjünk, hogy az esetek 51%-ában sikeresen tippeljünk. Ha nincs ilyen algoritmus, akkor azt mondjuk, hogy a generátor megjósolhatatlan.

Ez a két definíció ekvivalens: ha egy álvéletlen sorozat az igazitól megkülönböztethetetlen, akkor megjósolhatatlan, és viszont. Ez egyáltalában nem nyilvánvaló.

Még kevésbé nyilvánvaló az, hogy létezik elméletileg is jó generátor - ez a kérdés azonban nem fér bele ebbe az előadásba. Annyit mégis meg szeretnék jegyezni, hogy ez is azon alapszik, hogy míg két számot könnyű összeszorozni, nem könnyű egy számot tényezőire bontani.

Ezeknek az eredményeknek filozófiai tartalma is van. Van-e értelme valamit "kiszámíthatónak", "determináltnak" nevezni, ha csak "elvileg" számítható ki, ami azt jelenti, hogy a számítás a világ végezetéig tartana?