Cím: Algoritmikus vagy véletlen? II. rész
Szerző(k):  Benczúr András 
Füzet: 1992/február, 49 - 53. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek
Hivatkozás(ok):1992/március: Megjegyzés az Algoritmikus vagy véletlen című cikkhez

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az előző részben egy bolha üldözése során pár dolgot megtudtunk az algoritmusokról, speciálisan az algoritmusokkal megadható és az általános, "véletlen'' sorozatok közti különbségről. E különbségről sajnos csak annyi derült ki, hogy általános sorozat ‐ Cantor átlós elve szerint ‐ több van, mint algoritmikus, vannak programmal meg nem adható sorozatok. Láttunk is erre példát a megállási függvény "átlója'', H(n,n) például ilyen volt.
E sorozat, amely speciálisan 0-kból és 1-ekből áll, azonban aligha tekinthető egy pénzdobás (0=fej,1=írás) tipikus eredményének. Igen egyszerű például sok helyen meghatározni: hajtsuk végre az összes programot 1010 lépésig, nagy részük végeredményt fog szolgáltatni.
Nem tartanánk azt sem véletlennek, ha a bolha mindig éppen eggyel az előtt a mező előtt járna, amelyre mi, pl. az V. eset stratégiája szerint, csapnánk. Különösképpen pedig nem tudjuk a választ a legelőször feltett kérdésre: ha csak néhány, véges sok lépését ismerjük a bolhának (vagy egy fej-írás sorozatnak), honnan ered az az érzetünk, hogy ez szabályos, illetve véletlenszerű. Hiszen bármely sorozat véges sok eleme előállítható programmal (készítsük el e programot), a KONSTANS0(n) utasítás segítségével.

 

A Kolmogorov-komplexitás
 

Módosítsuk a bolhás feladatot úgy, hogy miután (mellé)csaptunk leendő áldozatunknak, meglátjuk, hol is volt valójában. Így a következő lépésben elkaphatjuk a bolhát, ha sikerül kifigyelnünk, milyen szabályt követ az ugrálása. Így a feladat első 4 változata 3 időegység alatt biztosan véget ér.
Mi a helyzet az ötödikkel? Tudjuk, hogy egy rögzített szabályt követ a bolha, ezt a szabályt induktívan kell kikövetkeztetnünk, hasonlóan a TV műsorokban, intelligenciatesztekben előforduló feladatokhoz. Célunk itt a legegyszerűbb szabály megtalálása. Például a 3, 5, 7 sorozatot biztosan 9-cel folytatnánk (páratlan számok), és bosszúsak lennénk, ha a bolha tovább ugrálna, mert a páratlan prímekre gondolt és 11 a folytatás.
Mit is jelent az, hogy egy szabály egyszerűbb a másiknál? Ezt megfoghatjuk matematikailag úgy, ha a szabályt leíró program hosszát vizsgáljuk. Vezessük be tehát egy n∈N számra (amelynek persze a már látott módon megfeleltethető egy x sorozat) a K(n) = {a legrövidebb program hossza, amely n-et előállítja} mennyiséget. Ezt a sorozat Kolmogorov-komplexitásának nevezzük, a híres, 1987-ben elhunyt szovjet matematikus után.
K(n) természetesen függ attól, hogy milyen "jó'' programnyelvet használunk. Azonban bármely gépen (ha nincs memóriakorlát) elkészíthető bármely programnyelv fordítója, amelynek hosszát a P nyelvben megírva jelölje CPQ, és a Q nyelvet fordítsa a P-re. Így a P és Q nyelvekhez tartozó KP és KQ komplexitásokra igaz lesz KP(n)≤KQ(n)+CPQ, minden n∈N esetén; CPQ n-től nem függ, hiszen a Q-beli programhoz még a CPQ hosszú fordítóprogramot kell hozzáilleszteni. Ehhez persze még az is kell, hogy a P és Q nyelvek ugyanazokat a jeleket ‐ pl. 0‐9, vessző stb. ‐ használják. Így, intuitíven
KP(x)≈KQ(x),  ha  KP(X)≫CPQ.
 

K(x) nem kiszámítható
 

Ha ismerjük K(x)-et, az x-et előállító legegyszerűbb szabályt meg is kereshetjük: a K(x) hosszú programokat kell lépésenként(!) végrehajtanunk (előfordulhatnak köztük olyanok is, amelyek végtelen ciklusba esnek), azaz az összes K(x) hosszú programot az összes t∈N lépésszámig ki kell próbálnunk, az egyik biztosan szolgáltatni fogja x-et. A próbálgatás módja pedig azonos a 2-dimenziós bolhaüldözéshez: számpárokat kell kipróbálnunk, az első paraméter a program sorszáma, a második pedig a t lépésszám.
 
 

Célul most a K(x)-et meghatározó algoritmus keresését tűzhetnénk ki. Most már azonban tudjuk, hogy nem minden függvény kiszámítható. K(x) meghatározását a H(k,n) megállási függvény ismeretében elvégezhetjük: kipróbáljuk hossz szerinti növekvő sorrendben az összes programot, amely nem esik végtelen ciklusba. Mivel azonban H(k,n) nem kiszámítható, kénytelenek vagyunk ismét csak a lépésenkénti kipróbálás ötletét használni. Például az ábrán látható sorrendben próbáljuk ki a programokat a megfelelő lépésszámig. Mivel minden véges(!) sorozatot elő tudunk állítani programmal, előbb-utóbb találunk is egy ilyent, pl. az n0-adikat a t0 végrehajtási idővel. Ha minden, az n0-adik programnál rövidebb program vagy véget ért ekkorra, vagy valamilyen módon bizonyítani tudjuk, hogy végtelen ciklusba esik (pl. 0 UGRIK0(0,0)), készen vagyunk. Általában azonban lesznek programok, amelyeket még nem próbáltunk ki elegendő sokáig, ezek között lehet, hogy valamelyik egyszerűbb szabályt szolgáltat x-re.
3. Tétel K(x)nem kiszámítható.
Bizonyítás. A "legkisebb, magyar nyelven ezer betűvel le nem írható szám'' tartalmi paradoxon ötletét vegyük át (ez a szám azért nem létezhet, mivel éppen most írtuk le, ezernél jóval kevesebb betűvel). Tekintsük tehát a legkisebb, C-nél nagyobb komplexitású számot, ahol C-t majd később választjuk meg. Ha K(x) kiszámítható volna, az összes számra kiszámítanánk, amíg az első C-nél nagyobbat el nem érjük. Tételezzük fel, hogy ez a program létezik, és C-t, mint adatot tartalmazza.
Legyen C0 a program hossza az adat nélkül. C-t, mint adatot legfeljebb log10C+1 decimális jeggyel leírhatjuk. Így egy x-et előállító programot kapunk, amelynek hossza
C0+log10C+1≥K(x)≥C,
azaz 10-et erre a hatványra emelve
C⋅10C0+1≥10C,10C0+1≥10C/C,
ahol 10C/C tetszőlegesen nagy lehet, tehát 10C0+1-nél is nagyobb. Ekkora C választásával tehát ellentmondásra jutunk. Itt persze szó sincs paradoxonról: indirekten azt igazoltuk, hogy K(x) mégsem kiszámítható. □
 

A véletlenszerűség és a komplexitás
 

Most már módunkban áll jobb jellemzését adni a véletlenszerűségnek. Egy algoritmikusan előállított végtelen sorozatot egy véges hosszúságú program szolgáltat: a kezdőszeletek komplexitása tehát egy megfelelő hossz után már nagyon kicsiny lesz. A véletlenszerűségérzet ezzel ellentétben a magas komplexitáshoz társul. De mekkora lehet egy x véges sorozat komplexitása? Biztosan nem lehet nagyobb mint a PRINT "x" utasítás megfelelő programnyelvre való fordítása, azaz l(x)+C, ahol l(x) a sorozatban szereplő számjegyek és vesszők összhossza, C pedig x-től nem, csak a programnyelvtől függ.
Másrészt tekintsük a programokat a már látott módon, a 0‐9 számjegyekkel és a vessző segítségével kódolva. Ekkor l-nél rövidebb program
1+11+112...+11l-1=11l-110<11l
darab van, míg olyan sorozat, amelynek a hossza l (az elválasztó vesszőkkel együtt, két egymást követő vessző közé ismét 0-t képzelve) 11l; így van olyan x sorozat, amelyre l(x)≤K(x).
Ráadásul az l+C hosszú sorozatoknak, amelyek száma 11l+C, már csak kis része, kevesebb mint 1/11C része lehet l-nél "egyszerűbb''.
Egy x véges sorozat véletlenszerűségét tehát úgy foghatjuk meg, hogy x-re l(x)≈K(x), azaz "nagy'' a komplexitása. A véletlen-érzetünk is megmagyarázható: a sorozatok nagy részére nincs igazán rövid leírás, az egyszerűen előállíthatók aránya kicsi. Így valóban ritkábban fordulnak elő a szabályos, mint a szabálytalan sorozatok. A legtöbb rögzített hosszúságú sorozatot csak a PRINT "x"-nek megfelelő eljárás állítja elő, ez pedig a bolha üldözése szempontjából csekély segítség, hiszen nem ad jóslatot a bolha következő lépésére.
 

Egy gyenge prímszámtétel
 

Végezetül lássunk a Kolmogorov-komplexitásra két, különböző területről származó alkalmazást.
Legyen p(n) az n-nél nem nagyobb prímek száma.*
Tétel. p(n)≥log2nlog2(log2n)-2, ha n elég nagy.
Bizonyításvázlat. Tekintsünk egy olyan számítógépet, amely kettes számrendszerbeli be- és kimenetekkel dolgozik. Legyen n egy véletlenszerű szám, azaz amelyre K(n)≥l(n)-C+1≥log2n-C ([log2n] darab bináris jegyből áll n). Tudjuk, hogy n=∏p<n prímPiαp, valamely αp természetes számokra. Mivel n≥pαp≥2αp, ezért αp≤log2n, így az αp-t leíró jegyek száma, l(αp)≤log2log2n.
Állítsuk elő azt a jelsorozatot, amely (log2log2n-1) egyesből, egy 0-ból (ezek αp hosszát határozzák meg) majd sorra p=2,3,5,... esetén αp-kből áll:
11...10︸log2log2n︸α2jegyei︸α3jegyei...︸αpjegyei︸p(n) darab n-nél kisebb prím
Ennek összhossza tehát (legfeljebb) (p(n)+1)log2log2n.
Tekintsünk egy programot, amely tartalmaz egy adatot. Megszámolja először az adat elején lévő egyeseket, az első 0-ig, majd ilyen hosszú "szeletekre'' vágja a további részt, így αp-ket előállítva. Végül pedig az
n=∏p prímpαp
kimenettel áll le.
Legyen e program hossza adat nélkül C1, adattal együtt tehát
C1+(p(n)+1)log2log2n.
E program előállítja n-et, tehát hossza K(n)-nél nem kisebb:
C1+(p(n)+1)log2log2n≥K(n)≥log2n-C2,
azaz
(Clog2log2n+1)+p(n)≥log2nlog2log2n.
Mivel log2log2n tetszőleges nagy lehet, van olyan n0, amelytől kezdve
(Clog2log2n+1)≤2. Ha n-t ennél nagyobbnak választjuk, a bizonyítandót kapjuk.□
 

Gödel nemteljességi tétele
 

Gödel tételének egy változata
Az is Hilbert egy kérdése volt akkor, hogy az aritmetika axiómái helyesen írják-e le az egész számok világát. Ez 1931-ben kiábrándító választ nyert: Kurt Gödel (1906‐1978) jött arra rá, hogy amennyiben az aritmetikának tetszőleges, algoritmussal felsorolható és ellentmondásmentes axiómarendszerét tekintjük, mindig léteznek olyan állítások, amelyek nem bizonyíthatók ebben az axiómarendszerben.
Meg fogok ilyen állításokat adni, előbb azonban ismét csak az aritmetikai állításokról és bizonyításokról alkotott intuitív képünket kell javítanunk. Hogy ez mennyire fontos, a következő példa mutatja. Mit mondjunk a következő állításról:
"Én nem vagyok bizonyítható''.


Ami bizonyítható, az igaz, így az állítás nem lehet hamis, hiszen akkor ő maga mondja ki, hogy bizonyítható. Tehát bebizonyítottuk, hogy az állítás igaz?
Hogyan oldható fel az ellentmondás? Úgy, hogy ezt az állítást egy formális rendszerben csak a következőképpen fogalmazhatjuk meg:
"Én nem vagyok bizonyítható az adott formális rendszerben'',


és ekkor bizonyításunk kívül esik a rendszeren, de az állítás valóban igaz. (A Gödel-tétel bizonyításai általábán ilyen típusú állítást adnak meg, formálisan.)
E példán látható, hogy mindig beszélhetünk egy objektumon pl. (N, összeadás, szorzás), igaz állításokról. Gödel tétele nem azt jelenti, hogy az egész számokra vonatkozó bizonyos állítások "kétféleképpen viselkedhetnek'', "mindössze'' annyit, hogy nem tudjuk őket az adott alapfogalmakban adott axiómákból levezetni. Ez azzal egyenértékű (ez is bizonyításra szoruló állítás!), hogy van két olyan objektum, amelyek nagyon hasonlítanak: érvényes rajtuk az axiómarendszer, azonban bizonyos állítások különböznek rajtuk. Az aritmetika esetén az egyik objektum az (N,+,*), ahhoz, hogy ezt a másik objektumtól elkülöníthessük, újabb axiómákra van szükség. De mi lenne, ha n összes igaz állítását axiómának tekintenénk? Igaz, hogy ez egy végtelen axiómarendszer lenne, de a végességet nem is követeltük meg. Viszont ahhoz, hogy legalábbis elő tudjunk tetszőleges axiómát állítani, ha szükségünk van rá, kell egy algoritmus, amely ezeket felsorolja. A tétel szerint ilyen nem fog létezni.
Fogjunk most hozzá az aritmetika nyelvének vizsgálatához. Alapfogalmak lehetnek a 0̲ szám, a rákövetkezés függvénye: S(n)=n+1, és az összeadás és szorzás függvények. N elemei előállíthatók, mint a 0̲ rákövetkezői. Mivel az axiómarendszernek más modellje is lehet, az újonnan definiált számokat jelöljük aláhúzással. Így 1̲=S(0̲),n+1̲=S(n̲)=S...S︸n+1(0̲).
Végül axiómák legyenek az összeadás, szorzás és a ≤ reláció legegyszerűbb ismert tulajdonságai: (1)m̲+n̲=p̲, ha m+n=p (mi tudjuk, hogy ez mely (m,n,p) hármasra teljesül, és erre kell a rendszert "megtanítanunk''),
(2)m̲*n̲=p̲, ha m⋅n=p (hasonlóan),
(3)x≤n̲ pontosan akkor, ha x=0̲,1̲,...,n-1̲ (x most nem aláhúzott, hiszen nem tudjuk, hogy előáll-e, mint S...S(0̲)).
Nem triviális, de igaz, hogy a programokkal, azaz kiszámítható függvényekkel kapcsolatos állítások megfogalmazhatók e nyelven, így pl. a K(x) komplexitás is.
A másik tény, amelyre szükségünk lesz, az, hogy az axiómákból következő bizonyításokat fel tudjuk sorolni egy programmal, feltéve, hogy maguk az axiómák felsorolhatók. (Persze így várni a Fermat‐sejtés bizonyítására olyan, mintha ABC sorrendben minden szöveget felírva akarnánk Shakespeare műveit megkapni.)
Most már következhet a
Tétel. Rögzítsünk egy, az aritmetikát (0̲,S,+,*,≤) tartalmazó rendszert és axióma rendszerét, amely a fenti axiómákat tartalmazza, ellentmondásmentes és programmal felsorolható. Ekkor van olyan C, hogy a "C≤K(x)'' igaz állítások ezen axiómából nem bizonyíthatók.(Tudjuk, hogy van olyan x, amelyre C≤K(x), így "C≤K(x)''-nek igaz állításnak kell lennie.)
Bizonyítás. Hasonlóan történik annak igazolásához, hogy K(x) nem kiszámítható. Ismét válasszunk egy nagy C-t és keressük meg a helyes bizonyítások felsorolásában az elsőt, amelynek konklúziója az, hogy valamely x-re K(x)≥C.
Így x előállítható annak a programnak a segítségével, amely felsorolja a helyes bizonyításokat. Ha C jóval nagyobb, mint e program hossza (emlékezzünk arra, hogy C-t, mint adatot kellett még a programban tárolni), ismét ellentmondásra jutunk, egy C-nél nagyobb komplexitású számot egyszerűbben állítunk elő. Itt azonban az ellentmondás csak úgy oldható fel, hogy "K(x)≥C'' állítást soha nem is találunk. Ezzel a tételt beláttuk. □
A C konstans elsősorban az axiómarendszer komplexitásától függ, hiszen a formálisan helyes bizonyításokat felsoroló program az axiómáktól függetlenül elkészíthető (az axiómák adatok lehetnek). E megfigyelés alapján Chaitin (1947 ‐) amerikai matematikus, akitől e bizonyítás szármázik, a tételt így foglalta össze:
"Ha csak egy 10 font súlyú axiómarendszerünk van, nem tudunk egy 20 font súlyú tételt levezetni belőle.''
 

*A prímszámtétel azt mondja ki, hogy limn→∞p(n)n/logn=1.