LOVÁSZ LÁSZLÓ

MIT KÍVÁNNAK A SZÁMÍTÓGÉPEK A MATEMATIKÁTÓL
ÉS MIT ADNAK NEKI?

Napjainkban teljesen magától értetődőnek tűnik, hogy munkánk során számítógépet használunk, internetezünk, bankkártyával fizetünk vagy meghallgatunk egy CD-lemezt. Ilyenkor talán végig sem gondoljuk, hogy ezek egyikét sem tehetnénk meg, ha nem jöttek volna létre a matematika új ágai: az algoritmuselmélet, a kriptográfia vagy a bonyolultságelmélet. Gondolnánk-e, hogy adatvédelmünk, a katonai létesítmények, a bankrendszer, s így a gazdaság biztonsága azon is múlik, hogy egy elég nagy szám felbontható-e belátható időn belül prímszámok szorzatára? Miért fontos tudni egy számról, hogy azt véletlen módon adták-e meg nekünk vagy valamilyen algoritmus eredményeként? Milyen régi problémák megoldásában segíthet nekünk a számítógép s melyekben nem? Ezekre az izgalmas, mindannyiunkat érintő kérdésekre keresi a választ az előadás.

I. BEVEZETÉS

A számítógépek a 20. század igazi forradalmát jelentik. Az elmúlt évszázad második felét szokás ,,atomkorszak”-ként emlegetni; a ,,számítógépek korszaka” azonban pontosabb leírás volna. Akár egy évnyi előadássorozatot is össze lehetne állítani a számítógépek, az információs technológia hatásáról a kultúra és a tudomány különböző területein. Ez az előadás csak a matematika szempontjából veszi szemügyre a számítógépeket.

Legjobb, ha mindjárt az elején felhívom a figyelmet valamire. A matematika az egzakt gondolkodásról szól, és nem lehet a matematikáról anélkül beszélni, hogy legalább egy kicsit ne kóstoljunk bele ebbe az egzakt gondolkodásba. Elkerülhetetlen tehát, hogy a hallgatókat, olvasókat legalábbis időnként arra kérjem, hogy együtt gondolkozzunk, hogy ne csak a tényeket, hanem azok logikáját is kövessék.

Mindjárt föl is teszek egy kérdést, mely gyakran fölvetődik, és melyre az első, átgondolatlan válaszunk könnyen az igazság ellenkezője lehet: Feleslegessé teszik-e a számítógépek a matematikát?

Minden nagy fejlődés sok olyan dolgot tesz fölöslegessé, mely korábban fontos, sőt alapvető volt. Odakerül-e a matematika is a logarléc és a gőzmozdony mellé? Látni fogjuk, hogy éppen ellenkezőleg, a számítógépek igénye a matematika új fejezeteit hívja létre és a régi fejezeteket egészen új megvilágításba helyezi. A számítógép új kérdéseket tesz fel a matematikának, és ezek a kérdések új fogalmak, új paradigmák kialakulásához vezetnek.

A probléma gyakran konkrétabb formában is megfogalmazódik: Nem teszi-e feleslegessé a hardver fejlődése a matematikai módszereket a programozásban? A hardver hihetetlen fejlődésen ment és megy keresztül. Ezt a fejlődést Moore törvényével lehet leírni, aki az Intel egyik alapítója, és 1965-ben azt a megfigyelést tette, hogy az egy-egy integrált áramkörben használt tranzisztorok száma mintegy 2 évenként megduplázódik. Ez a gyors fejlődés azóta is tart.

Az 1. képen Neumann János látható, aki a számítógépek egyik atyja. A háttérben levő gépen jól láthatók a rádiócsövek; minden ilyen cső egy-egy számítási alapegységet, „kaput” valósít meg. Ma egy négyzetcentiméteren 50 millió ilyen kapu van!

Sok olyan feladat van, amit csak nehezen, bonyolult trükköket bevetve tudunk megoldani, de egy évvel később a sokkal gyorsabb, nagyobb kapacitású gépek játszva megcsinálják őket. Úgy tűnhet tehát, hogy kár a bonyolultabb matematikai módszereket erőltetni. Ám ha jobban megnézzük, kiderül, hogy éppen ellenkezőleg: a technikai fejlődés olyan feladatokat hoz létre, amiket „trükkös” gondolkodással már nem lehet megoldani, csak komoly matematikai módszerekkel.

Meg lehet-e érteni például egzakt matematikai gondolkodás nélkül az internetet, ami több százmillió számítógépet köt össze egymással? Meg lehet-e tervezni egzakt matematikai módszerek nélkül egy modern integrált áramkört, ahol 50 millió számítási alapegység van egy négyzetcentiméteren összezsúfolva? Lehet-e pontos matematikai modellezés nélkül gondolkodni egy olyan rendszer biztonságáról, amit milliárdnyi ember használ, akiket nem ismerünk – de tudjuk, hogy vannak köztük bűnözők és terroristák is?

A matematika tehát nagyon is sokat tud nyújtani a számítástechnikának. De mit kap cserébe? Nagyon sok mindent: izgalmas új fogalmakat, problémákat és módszereket, új kísérletezési lehetőségeket. Ezek közül nézünk meg egy párat a következőkben.

II. A BONYOLULTSÁG ÚJ FOGALMA

A bonyolultság fogalma hasonló fejlődésen ment át az utóbbi 50 évben, mint sok más alapvető fogalom. Először egy megértést akadályozó körülményt jelentett (vagy talán csak kényelmes kifogást?). Ha egy jelenség vagy struktúra túl bonyolult, akkor a kutatás során megkerüljük, leegyszerűsítjük vagy részeire bontjuk. A következő fázist az jelenti a fogalom történetében, amikor a tudós elkezdi a bonyolultságot mint önálló jelenséget szemlélni: kidolgozza, hogy hogyan lehet mérni, szabályokat és törvényeket állapít meg, kapcsolatba hozza más, korábban megismert dolgokkal. Végül jelentkezik a mérnök, hogy a bonyolultságot eszközként használja fontos tervezési problémák megoldására: az adatvédelem, az elektronikus posta, a kereskedelem, a pénzforgalom biztonsága ma nagyrészt a bonyolultság fogalmán és annak tulajdonságain alapul.

A 19. századi matematika egyik nagy sikere a végtelen fogalmának megragadása volt. Ennek bűvölete olyan erős, hogy hajlamosak vagyunk mindenre, ami véges, rálegyinteni: „Véges sok eset van, amit végig lehet nézni!”. A számítógépek megjelenése azt eredményezte, hogy rájöttünk: a véges nagyon nagy lehet, bekövetkezhet az „exponenciális robbanás”.

II. 1. Exponenciális robbanás

A sakkjáték feltalálójáról szóló klasszikus történet szerint az unalma elűzéséért hálás király felajánlotta neki, hogy azt kívánhat jutalmul, amit akar. A feltaláló azt kérte, hogy a sakktábla első mezejére tegyenek egy búzaszemet, a másodikra kettőt, a harmadikra négyet, a negyedikre nyolcat, és így tovább, minden mezőre kétszer annyit, mint az előzőre. A király nagyon megörült, hogy ilyen olcsón megúszta, de aztán rá kellett jönnie, hogy nemcsak, hogy a 10-12-ik mezőtől már nem férnek el a búzaszemek, de a tábla közepe táján már birodalmának teljes búzatermése sem lett volna elegendő, hogy ígéretét betartsa.

Ezt a jelenséget, hogy ha egy mennyiséget ismételten duplázunk (vagy bármilyen egynél nagyobb számmal szorzunk), akkor igen gyorsan növekszik, exponenciális robbanásnak hívjuk. Moore említett törvényében az a meglepő hogy az informatikában bekövetkezett exponenciális robbanás ilyen sokáig tud tartani. Az 1960-as évek környezetvédelmi forradalma mögött az áll, hogy egyre többen értették meg, hogy az exponenciális növekedés nem tarthat örökké, sem a népesség, sem a termelés, sem a fogyasztás területén.

A számítástudományban az exponenciális robbanás leggyakrabban akkor lép fel, ha azt a kijelentést, hogy „Véges sok eset van, amit végig lehet nézni!”, megpróbáljuk közelebbről vizsgálni. Mondjuk, az esetek megkülönböztetéséhez először is két alapesetet kell megkülönböztetni; aztán ezek mindegyikén belül két újabb eset van stb. Ezt a logikai helyzetet a 2. ábrán látható hálózattal, ún. bináris fával ábrázolhatjuk. Látható, hogy a végignézendő esetek száma már néhány elágazás után is ugrásszerűen nő, és bekövetkezik az exponenciális robbanás. Ha algoritmusunk egy ilyen fát kell hogy végigvizsgáljon, akkor a modern számítógépek mondjuk 30 szint mélységig még bírják, csakhogy minden egyes újabb szint megduplázza az esetek számát. Itt még Moore törvénye sem segít: ha 10 évig várunk, akkor mondjuk 5 szinttel tudunk továbbmenni.

Ezért aztán a számítástudományban elég hamar megfogalmazódott, hogy olyan algoritmusok tervezésére kell törekedni, melyek lépésszáma a feladat méretével csak mérsékelten nő, úgy, mint a méret egy hatványa, nem pedig exponenciálisan. Tehát ha a feladat mérete n, akkor a lépésszám lehet n² vagy n³, de nem lehet 2ⁿ. Az ilyen algoritmust polinomiálisnak szokás nevezni. A kétfajta növekedés közötti különbséget úgy lehet a legjobban szemléltetni, ha elgondoljuk, hogy mekkora teljesítménynövekedést lehet várni a technológia fejlődésétől. Tegyük fel, hogy mind az A algoritmus, mind a B algoritmus ma 50 bemenő adattal tud egy adott problémát megoldani. Az A algoritmus lépésszáma úgy nő a bemenő adatok számával, mint n³, a B algoritmusé, mint 2ⁿ. Ha várunk 10 évet, és a számítógép teljesítménye 32-szer akkora lesz, mint ma (Moore törvénye szerint), akkor az A algoritmus már 150 bemenő adattal bír el, míg a B algoritmus teljesítőképessége csak 55 adatra emelkedik.

II. 2. Primtesztelés és -faktorizáció

Egy pozitív egész számot prímszámnak nevezünk, ha 1-en és önmagán kívül más egész számmal nem osztható. Az 1-et nem tekintjük prímnek, de utána aztán sok példát látunk: 2, 3, 5, 7, 11, 13 stb. Azokat a természetes számokat, melyek nem prímek, fel lehet bontani prímszámok szorzatára, például 6=2*3, 40=2*2*2*5 stb. - ezt a felbontást nevezzük prímfaktorizációnak.

A prímszámokkal kapcsolatban két fontos algoritmikus problémát fogalmazhatunk meg: ha adott egy k jegyű szám, hogyan tudjuk eldönteni róla, hogy prímszám-e; és ha nem prímszám, hogyan tudjuk megtalálni a prímtényezőit?

Mindkét kérdésre könnyű ,,véges” választ adni: csak ki kell próbálni, hogy osztható-e a szám 2-vel, 3-mal, 4-gyel, 5-tel stb. Ha találunk olyan számot, amelyik osztója, akkor tudjuk, hogy nem prímszám, és a felbontást is könnyű megcsinálni. A baj ezzel az, hogy iszonyú sok számot kell kiprobálni: ahhoz, hogy egy 100 jegyű számról eldöntsük, hogy prím-e, 10¹⁰⁰ számot kell kipróbálni, ami nagyobb, mint a világegyetem bármilyen paramétere. Kis ravaszsággal észrevehetjük, hogy elegendő a szám négyzetgyökéig kipróbálni a számokat. De ez sem segít eleget: egy 100 jegyű szám négyzetgyöke 50 jegyű, és 10⁵⁰ is messze túl van a lehetőségek határán.

Kiderül, hogy az első kérdés sokkal könnyebb, mint a második: olyan hatékony (polinomiális) algoritmusok vannak, amelyek akár 1000 jegyű számról is könnyedén eldöntik, hogy prím-e. A tényezőkre bontásra azonban csak olyan algoritmus ismert, amely lényegében exponenciális: 100-nál több jegy esetén már csak nagy üggyel-bajjal működnek, 150 jegy fölött pedig egyáltalában nem. Látni fogjuk, hogy ennek az egyszerű ténynek hallatlan gyakorlati következményei vannak.

Hogyan lehetséges, hogy a prímfaktorizáció ennyivel nehezebb, mint a prímtesztelés? Azt gondolnánk, hogy mindegyikhez végig kell próbálni az adott számnál kisebb számokat, hogy nem osztható-e velük az adott szám. Nyilvánvaló, hogy ez nagyon hosszadalmas lenne, ezért valahogy másképp kell eljárnunk. A hatékony prímtesztelő algoritmusok az ún. ,,kis” Fermat-tételen alapulnak (a ,,kis” jelző nem a tétel fontosságára utal, hanem azért használjuk, hogy megkülönböztessük a csak nemrégen bebizonyított „nagy” Fermat-tételtől. Fermat, a nagy 17. századi francia matematikus csak az előbbinek a bizonyítását adta meg.)

Fermat tétele szerint, ha p prímszám, és a tetszőleges egész szám, akkor

p | a^p-a

(p osztója az a^p-a számnak). Például, 2⁵-2=30 osztható 5-tel. Ha egy p számról el akarjuk dönteni, hogy prímszám-e, akkor megnézzük, hogy 2^p-2, 3^p-3 stb. oszthatók-e p-vel. Ellentétben a fenti egyszerű teszttel, ezt nem kell nagyon sok számra kipróbálni, elegendő csak néhányra.

(Sok mindent söpörtem itt a szőnyeg alá: néhány p számra ez a módszer hamis pozitív eredményt ad, ezért kicsit módosítani kell; nagy számok nagyon nagy hatványaival kell számolni, ami megoldható, de nem nyilvánvaló, hogyan stb. De mindezeket megoldva ez a teszt, melyet Miller-Rabin-tesztnek hívnak, mint láttuk, nagyon jól működik.)

III. A VÉLETLEN ÚJ FOGALMA(I)

A véletlen a modern tudomány egyik sarkalatos fogalma. Szinte minden tudomány lépten-nyomon használ olyan modelleket, melyekben a jelenségek véletlen, statisztikus jellege dominál.

Ugyanakkor a véletlen igen nehéz fogalom is. Véletlen-e az, hogy egy földobott pénz fejre vagy írásra esik? Ha jól meggondoljuk, miért is ne tudná egy igazán éles szemű és gyors eszű ember azalatt, amíg a pénz fölfelé száll, megfigyelni a pályáját, perdületét és amit csak még kell, és ebből kiszámítani, hogy melyik oldalára fog esni? A valóságban (talán a kvantumfizikát leszámítva) csupa olyan „véletlen” jelenséggel találkozunk, melyek igazából nem véletlenek, csak megjósolásukhoz nem áll rendelkezésre elegendő adat és idő.

III. 1. Mitől nem véletlen egy sorozat?

Nézzük a véletlen legegyszerűbb matematikai modelljét. Dobjunk fel egy pénzdarabot mondjuk 100-szor, és írjuk le, hogy fejet vagy írást kapunk. Valami olyasmit fogunk látni, mint amit a 3. ábra mutat.

Tényleg véletlen pénzdobálással kaptam ezt a sorozatot? (Nem árulom el.) Ezt a kérdést nem is könnyű eldönteni. Persze ha valami könnyebbet kérdeznék, például a 4. ábrán látható sorozatot,

akkor mindenki azonnal látná, hogy ez nem lehet véletlen. Tudjuk, hogy a pénzfeldobásnál ugyanannyi a fej, mint az írás valószínűsége, ezért egy hosszú

pénzfeldobás-sorozatban körülbelül ugyanannyi fej kell legyen, mint írás.

Nézzünk akkor egy újabb sorozatot! (5. ábra) Ebben ugyanannyi fej van, mint írás, mégis nyilvánvaló, hogy ez se véletlen. (Mondjuk, érvelhetünk azzal, hogy a páros helyeken is fele-fele arányban kellene fejet és írást látni.)

Nézzük a következőt! (6. ábra) Ez már sokkal kevésbé szabályos, sokkal véletlenszerűbb, de azért gyanús. Aki jártas a valószínűségszámításban, rögtön látja, hogy túl gyakran váltakozik, nincsen benne például 3 egyforma betű egymás után. De a legmeggyőzőbb, ha elmondom: a sorozat k-ik eleme ☺, ha a k-1 szám kettes számrendszerbeli alakjában az 1-esek száma páratlan, és ☻, ha páros. Noha a sorozat meglehetősen szabálytalan, igen egyszerű szabállyal leírható, tehát egyáltalában nem véletlenszerű.

Nézzünk most egy számsorozatot is! (7. ábra) Véletlen-e ez? Gondolom, többen észrevették, hogy ezek egyszerűen a "pi" jegyei.

Még egy sorozatot nézzünk meg! (8. ábra) Ez már igazán véletlenszerűnek tűnik! Még a valószínűségszámításban jártas olvasó is nehezen találna kivetnivalót benne. Pedig ez is "pi", csak most 2-es számrendszerben van felírva.

III. 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.

A 30-as években Kolmogorov egészen más úton elindulva, az analízis eszközeit (a mértékelméletet) felhasználva alapozta meg a valószínűség fogalmát. Ez matematikailag nagyon jól használható volt, azonnal elterjedt, és mindenki úgy tekintette, hogy ezzel a probléma meg van oldva. Kivéve magát Kolmogorovot, aki a 60-as években visszanyúlt von Mises kísérletéhez, és azt úgy fejlesztette tovább, hogy matematikailag használható lett. Ezzel nagy lépést tett a véletlen nehéz fogalmának megértése felé.

Egy sorozat információtartalmának a definíciója a valószínűség fogalmától függetlenül is sok izgalmas megoldatlan kérdéshez vezet: Mekkora a genetikus kód, például egy emberi kromoszóma információtartalma? Mekkora az agy bonyolultsága? Milyen nagyságrendű az egész világegyetem bonyolultsága?

III. 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 ½ 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?

IV. A BIZONYÍTÁS ÚJ FOGALMA

A bizonyítás a matematika lelke, a görög tudomány talán legfontosabb alkotása. Mégis, az iskolai matematikatanításból sokszor kimarad. Még egyetemi hallgatók is gyakran nem értik, miért van rá szükség: ,,Elhisszük mi a tanár úrnak, minek azt bizonygatni.'' (Remélem, ez csak amerikai tapasztalatom).

A Pitagorasz-tételre már nagyon-nagyon sok bizonyítást talált az emberiség, és világos, hogy a bizonyításon nem azért kell végigmenni, hogy a tétel helyességéről még jobban meg legyünk győzve, hanem azért, hogy a bizonyításban szereplő matematikai módszereket elsajátítsuk. A programok helyessége, a kommunikációs protokollok biztonsága azonban nap mint nap bizonyítást igényel(ne).

IV. 1. Interaktív bizonyítás

Még érdekesebb azonban, hogy az infomatika a bizonyítás újszerű fogalmához is elvezet: az interaktív bizonyításhoz.

Alan Turing angol matematikus, a számítógéptudomány egyik megalkotója azon gondolkodott, hogy vajon hogyan lehet megkülönböztetni egy nagyon fejlett számítógépet egy embertől. Azt a kísérletet javasolta, hogy egy szobába ültessünk be egy embert egy képernyővel és billentyűzettel, míg a másik szobába vagy egy másik embert ültessünk hasonló képernyővel és billentyűzettel, vagy egy számítógépet tegyünk. Az első ember kérdéseket tehet fel, vagy bármi egyéb módon társaloghat a másik szobában levő lénnyel, és el kell döntenie ennek alapján, hogy emberrel vagy géppel áll-e szemben. Ezt a kísérletet nevezik Turing-tesztnek.

Hinnénk-e, hogy ezt a nyilvánvalóan csak gondolatkísérletnek szánt tesztet naponta sok ezerszer végzik el? Ha valaki például új e-mail címet akar csinálni magának, ilyesféle kérdéssel találkozhat: "Kérjük, gépelje be az alábbi betűket", és kicsit piszkos alapon néhány kuszán odaírt betűt lát. (12. ábra)

Ha valaki nem érti, mire való ez, rákattinthat a „Miért?” feliratra, és megtudja, hogy azért van erre szükség, mert sok program van, ami automatizálja a címek létrehozását, hogy aztán hirdetéseket küldjön szét róluk, vagy ami rosszabb, levelek tömeges küldésével megbénítson valakit. A képen az emberi szem könnyedén felismeri a betűket, de egy számítógépet (ma még legalábbis) a betűk torzulásai és a kusza vonalak megtévesztenek, így a programozott címgenerálást ki lehet szűrni.

Látszik tehát, hogy a mai számítógépek még nagyon gyorsan megbuknak a Turing-teszten, bár érdemes azt is megemlíteni, hogy itt a tesztet magát nem ember, hanem egy számítógép hajtja végre.

A fenti eljárás az interaktiv bizonyítás szép példája: két résztvevő van, és ebben az esetben a Bizonyító azt a „tételt” akarja bebizonyítani, hogy ő ember. A hagyományos matematikában a tételhez hozzá lehet csatolni a bizonyítást – itt azonban van egy Ellenőr,

aki egy vagy több kérdést tesz föl, és a „bizonyítás” a kérdéstől függ. Ez a séma sokkal erősebb a hagyományos bizonyítási formáknál – gondoljunk csak bele, hogyan tudnánk kérdés nélkül bebizonyítani, hogy emberek vagyunk?

Érdemes azt is megjegyezni, hogy a séma ereje a kérdés (a kusza betűsorozat) véletlen voltán múlik. Ha mindenkitől ugyanazt kérdezné vagy akár csak előre kiszámítható kérdést tenne fel, könnyű volna egy számítógépet úgy programozni, hogy az a jó választ adja. A jó véletlen-generátor tehát ennek a protokollnak is elengedhetetlen része!

IV. 2. Elektronikus boríték

Hasonló interaktív bizonyítások lépten-nyomon előfordulnak – gondoljunk a jelszavakra, az ,,okos kártyákra” stb. Számítógépes hálózataink biztonsága nagyrészt az ilyen bizonyításokon múlik. Hadd mutassak be egy nagyon leegyszerűsített példát. Tegyük fel, hogy Aliz és Béla interneten keresztül sakkoznak. Beesteledett, és meg kell szakítani a mérkőzést. Hagyományos sakkversenyen ilyenkor az történik, hogy mondjuk Alíz eldönti az utolsó lépést, de nem teszi meg a táblán, hanem borítékolja és odaadja a bírónak. A borítékot Béla csak másnap nyithatja ki. Így egyikük sem ismeri a másik utolsó lépését, ezért nincs az a nagy előnye, hogy egész éjjel gondolkodhat a lépésén.

De most nincs bíró és nincs boríték. Alíz üzenhet valamit Bélának este, és megmondhatja a lépését másnap reggel, de mit üzenjen este? Ha már esti üzenetével elkötelezi magát, akkor Béla előnyben lesz; ha nem, akkor Alíz lesz előnyben, mert megváltoztathatja a lépést az éjjel folyamán. A hagyományos információelmélet szerint a „borítékolás” lehetetlen.

A bonyolultságelmélet azonban megoldást kínál. Előre megállapodnak abban, hogy a lépéseket egy-egy négyjegyű számmal írjak le: például Kf3 helyett azt mondják, hogy 9083. Ezek után Alíz választ magának két 100 jegyű prímszámot, amelyek közül a kisebbik úgy kezdődik, hogy 9083... (Láttuk, hogy számítógéppel nem nehéz ellenőrizni, hogy egy szám prímszám-e; be lehet bizonyítani a klasszikus matematika mély eszközeit felhasználva, hogy ha néhány száz 100 jegyű számot találomra kipróbál, ezek között lesz prím.) Legyen ez a két szám p és q, ahol p<q. Este Alíz elküldi a pq szorzatot Bélának, reggel pedig elküldi a két tényezőt (ami a boríték felbontásának felel meg).

Láthatjuk, hogy Béla már előző este megkapta a teljes információt: egy körülbelül 200 jegyű természetes számot, melynek a kisebbik prímtényezőjéből az első 4 jegy megadja Alíz lépését. De mivel a számot nem tudja hatékonyan tényezőire bontani, a lépést másnap reggelig (vagy akár évekig) nem tudja kiolvasni. Ezt a „titkot” hét pecsétként őrzi a számítási bonyolultság.

(Egyébként Béla jól teszi, ha ellenőrzi, hogy p és q tényleg prímek. Aki szeret logikai feladatokon eltöprengeni, belegondolhat, miért van erre szükség.)

Ennél sokkal bonyolultabb módon, de azért hasonló gondolatokat használva valósíthatók meg digitálisan a társadalmi érintkezés olyan fontos elemei, mint a mások által felbonthatalan boríték (titkosírás), elismervény, számla, aláírás és annak hitelesítése, vízjel stb.

V. KLASSZIKUS KÉRDÉSEK ÚJ MEGVILÁGÍTÁSBAN

A klasszikus matematikát sokan elefántcsonttoronynak látják. Godfrey Hardy, aki a prímszámok elméletének egyik legkiemelkedőbb kutatója volt a 20. század első felében, ezt írja Egy matematikus védekezése című könyvében:

Soha nem tettem semmi ,,hasznosat”. Semelyik felfedezésem sem volt közvetlenül vagy közvetve jó vagy rossz hatással a világ folyására, és nem valószínű, hogy valaha is hatással lesz...

Az ,,igazi" matematikusok ,,igazi" matematikája, Fermat és Euler és Gauss és Abel és Riemann matematikája csaknem teljesen ,,haszontalan''.

Amikor az interneten vásárolunk vagy bankügyeket intézünk, számítógépünknek több száz jegyű számokról kell eldöntenie, hogy primek-e – tizedmásodpercek alatt. Ehhez Fermat tételét használja. A különböző számítógépes protokollok, biztonsági módszerek a Hardy által felsorolt nagyságok szinte mindegyikének a munkájára építenek.

Ha azt kérdezzük, hogy melyik az a megoldatlan matematikai probléma, melynek a legnagyobb a gyakorlati jelentősége, azt hiszem, egyértelmű a válasz: Fel lehet-e egy mondjuk 1000 jegyű számot hatékonyan (nem-csillagászati idő alatt) prímtényezőire bontani?

Azt hiszem azonban, hogy ezek a tények Hardy kutatási elveit legalább annyira alátámasztják, mint amennyire az állításait cáfolják. Ha ezeket a nagyságokat csak kutatásuk közvetlen haszna motiválta volna és nem a matematikai kérdések szépsége, a megismerés vágya, akkor ma nem lennének eszközeink a számítógép-rendszerek biztonságának védelmére.

Kislexikon

Algoritmus
Legáltalánosabb értelemben tervszerűség, egy elvégzendő cselekvéssorozat megtervezése lépésről lépésre.

Álvéletlenszámok
Kellően bonyolult algoritmussal előállított számsorozat, ami a véletlen számsorozat bizonyos jegyeit viseli magán.

Bináris fa
Olyan fa (gráf), melynek minden ága (éle) tovább ágazik kétfelé.

Exponenciális robbanás
Azon jelenség, hogy ha egy mennyiséget ismételten egy 1-nél nagyobb számmal szorzunk, akkor az igen gyorsan (robbanásszerűen) növekszik.

Információtartalom
Egy sorozat vagy egyéb struktúra információtartalma az, hogy milyen hosszú a lehető legrövidebb leírása a lehető leghatékonyabb kódolást használva.

Moore-törvény
Moore 1965-ben megfigyelte, hogy egy-egy integrált áramkörben használt tranzisztorok száma mintegy kétévenként megduplázódik.

Polinomiális algoritmus
Olyan algoritmus, mely esetén a feladat lépésszáma a feladat méretével úgy nő, mint a méret egy hatványa.

Prímfaktorizáció
A nemprím egész számok felbontása prímszámok szorzatára. Pl. 90 = 2*3*3*5.

Prímszám
Olyan egész szám, melynek csak az 1 és önmaga az osztója.

Turing-teszt
Gondolatkísérlet, mely azt hivatott eldönteni, hogy hogyan lehet egy nagyon fejlett számítógépet megkülönböztetni egy embertől.

Véletlenszám-generátor
Álvéletlen-számsorozatot előállító algoritmus.

Bibliográfia

Aho, A.V., Hopcroft, J.E., Ullman J.D.: Számítógépalgoritmusok tervezése és analízise, Műszaki Könyvkiadó, Budapest, 1982.

Gács P., Lovász L.: Algoritmusok, Műszaki Könyvkiadó, Budapest, 1978; Tankönyvkiadó, Budapest, 1987.

Goldreich, O.: Modern Cryptography: Probabilistic Proofs and Pseudorandomness, Springer-Verlag, In: Algorithms and Combinatorics, Vol 17, 1998.

Lovász L.: Algoritmusok bonyolultsága, ELTE egyetemi jegyzet.

Luby, M. Pseudorandomness and Cryptographic Applications, Princeton, NJ: Princeton University Press, 1996.

Rónyai L., Ivanyos G., Szabó R.:  Algoritmusok, TYPOTEX, Budapest, 1998.

Lovász L.: Egységes tudomány-e a matematika? In: Természet Világa, Matematika különszám, 1998.

Lovász L.: Véletlen és álvéletlen, In: Természet Világa, Informatika különszám, 2000.

Lovász, L.: Information and complexity (how to measure them? In:  The Emergence of Complexity in Mathematics, Physics, Chemistry and Biology (ed. B. Pullman),  Pontifical Academy of Sciences, Vatican City, Princeton University Press, 1996: 65-80.