Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

2. Alkatrészek összekapcsolása

2. Alkatrészek összekapcsolása

Próbáljunk meg számítógépet építeni. Szereztünk integrált áramköröket, mindegyiknek vannak „bemenetei” és egy „kimenete”. A bemenetekre többféle jelet vezethetünk, és ekkor a kimeneten is megjelenik egy jel. Ezeket az alkatrészeket egymáshoz csatlakoztathatjuk, azaz kimeneteket hozzáforraszthatunk bemenetekhez (egy kimenetet több bemenethez is, de egy bemenethez legfeljebb egy kimenet csatlakozhat). Az így kapott gép összetett számításokat tud végezni: a szabadon maradó bemenetekre jeleket vezetünk, és megnézzük egy szabadon maradó kimeneten kapott jeleket. Az ilyen „gépeket” általában logikai hálózatoknak nevezik. Ezek azért fontosak, mert a segítségükkel algoritmusokat lehet modellezni. Mi most nem ebbe az irányba haladunk, hanem egy algebrai problémát vizsgálunk: azt, hogy adott típusú alkatrészekből milyen gépeket lehet összerakni.

Például képzeljük azt, hogy háromféle alkatrészünk van, és összesen csak kétféle jel fordulhat elő: az IGEN ( I ) és a NEM ( N ). Az első fajta alkatrésznek két bemenete van, és a kimeneten akkor kapunk I -t, ha mindkét bemenet I volt, különben N -et kapunk. Az ilyen integrált áramkört „ÉS”-kapunak is szokás nevezni. A második fajta alkatrésznek is két bemenete van, de pont fordítva működik: a kimenet pontosan akkor lesz N , ha mindkét bemenet az volt (ez a „VAGY”-kapu). Végül a harmadik fajta alkatrésznek egyetlen bemenete van: ha ide N érkezik, akkor a kimeneten az I -t kapjuk, ha pedig a bemenet értéke I , akkor a kimeneté N („NEM”-kapu).

2.1. Kérdés. Összerakható-e ÉS- és NEM-kapukból olyan gép, ami a VAGY-kaput modellezi?

Erre a kérdésre könnyű válaszolni: az ÉS-kapu mindkét bemenetére, és a kimenetére is rákötünk egy-egy NEM kaput. A négyféle lehetséges bemeneti értékpárt megvizsgálva azonnal látjuk, hogy ez a konstrukció VAGY-kapuként működik.

2.2. Kérdés. Összerakható-e ÉS- és VAGY-kapukból olyan gép, ami a NEM-kaput modellezi?

Erre a kérdésre nemleges a válasz. Ennek bizonyítása ugyanolyan nehézséget vet fel, mint a szóprobléma esetében! Nem bizonyíthatunk úgy, mint az előbb (hogy megépítjük a kívánt gépet), hanem éppen ellenkezőleg: át kell tekintenünk egy alkalmas ötlet segítségével az összes lehetséges (végtelen sok) gépet, és mindről be kell látnunk, hogy nem jó.

Minden ilyen jellegű bizonyításban egy további problémával is foglalkoznunk kell. Gépet építeni akkor is tudunk, ha még nincs pontosan definiálva, hogy általában mit értünk gép alatt: utólag is elvitatkozhatunk azon, hogy amit építettünk, az gép-e. Sőt a gép precíz fogalmának kialakítása pontosan ilyen viták során történhet. Ha azonban azt akarjuk belátni, hogy nem létezik adott tulajdonságú gép (vagy eljárás, bizonyítás, stb.), akkor már előre tudnunk kell, hogy precízen mit is értünk gép (eljárás, bizonyítás) alatt. Az emberiség évezredeken át „bizonyított” tételeket, de a bizonyítás pontos fogalmát csak mintegy száz évvel ezelőtt, a matematikai logika alkotta meg. Ez tette lehetővé, hogy bizonyos állításokról megmutassuk, hogy nem bizonyíthatók, vagy akár eldönthetetlenek.

Alkossunk tehát matematikai modellt a gép fogalmára. Egy-egy integrált áramkör függvényként viselkedik, ami az összes lehetséges jelek J halmazán van értelmezve, annyi változós, ahány bemenet van, a függvény értéke pedig a kimeneten kapott jel. Az egymáshoz való forrasztások azt jelentik, hogy ezeket a függvényeket korlátlanul szabad egymásba helyettesíteni. Például ha e , v és n jelenti az ÉS-, a VAGY-, és a NEM-kapukhoz tartozó függvényeket (ahol most J elemei I és N ), akkor

v ( x , y ) = n ( e ( n ( x ) , n ( y ) ) )

az imént épített gépnek felel meg.

A 2.2. Kérdés megválaszolásához tegyük fel, hogy összeállítottunk egy g ( x ) függvényt az e és v függvényekből. Tudunk-e találni egy olyan tulajdonságot, ami ennek megvan, de a NEM-kapunak nincs meg? Helyettesítsünk be I -t az x helyére. Mivel e ( I , I ) = I és v ( I , I ) = I , akárhogyan is írtuk fel a g függvényt, minden helyettesítésnél I -t kapunk, és így g ( I ) = I is teljesül. Vagyis g nem lehet NEM-kapu.

Kis erőfeszítéssel pontosan meg tudjuk azt is mondani, hogy kapuinkból milyen gépeket lehet összerakni, és milyeneket nem.

2.3. Feladat. Mutassuk meg, hogy ÉS-, VAGY-, és NEM-kapukból tetszőleges gép összerakható (azaz mindegyik f : J n J függvény megkapható úgy, hogy az e , v , n függvényeket egymásba helyettesítgetjük).

2.4. Feladat. Adjunk meg minden véges jelhalmazon olyan két bemenetű IC-t (azaz egy kétváltozós függvényt), aminek példányaiból tetszőleges gép összerakható.

A 2.4. Feladatban nem könnyű megtalálni egy kívánt tulajdonságú függvényt. A matematikában gyakran előfordul, hogy valamit nehéz megkonstruálni, de ha véletlenszerűen választunk, akkor jó eséllyel megfelelő dolgot kapunk. Képzeljük el tehát, hogy az összes lehetséges alkatrészek közül véletlenszerűen választjuk ki azokat, amelyekből gépeket szeretnénk építeni. Az nyilvánvaló, hogy ha csupa egyváltozós függvényt veszünk, akkor ezekből csak egyváltozós függvényt lehet összerakni. A meglepő az, hogy ha nem ezt tesszük, akkor nagy valószínűséggel az összes gép összerakható belőlük. A pontos eredmény, Murszkij tétele, a következő.

2.5. Tétel. Adott egy n elemű jelhalmaz. Ha véletlenszerűen kiválasztunk egy legalább háromváltozós függvényt, akkor annak a valószínűsége, hogy ezzel mindegyik véges változós függvény kifejezhető, 1-hez tart, ha n ? . Ugyanez igaz akkor is, ha egy kétváltozós függvényt, és tőle függetlenül egy másik (akár egyváltozós) függvényt választunk ki. Végül abban az esetben, ha csak egy kétváltozós függvényt választunk ki véletlenszerűen, akkor a fenti valószínűség 1 / e -hez tart.

Az itt szereplő e betű egy számot jelöl, melynek közelítő értéke e = 2 . 71828 . Ez a szám egy nevezetes analízisbeli határérték, ami misztikus módon egyéb matematikai (például prímszámokkal kapcsolatos) tételekben is megjelenik. Érdemes elmondani, hogyan jön be Murszkij tételében az 1 / e szám. Legyen a véletlenszerűen választott kétváltozós függvény az f . Ha van olyan j jel, amelyre f ( j , j ) = j , akkor mint láttuk, bárhogyan is helyettesítgetjük f -et önmagába, a kapott g függvényre is teljesül, hogy g ( j , j , , j ) = j , tehát ebben az esetben biztosan nem kapjuk meg az összes függvényt. Mi annak a valószínűsége, hogy ilyen j jel nincs?

Az f függvény megadásához f ( x , y ) értékét kell megmondanunk minden x és y jelre. Tehát összesen n 2 függvényértéket kell megadnunk, mindegyik n -féle lehet. Vagyis az összes kétváltozós függvények száma n n 2 . Ezek közül azok lesznek „jók” nekünk, ahol az f ( j , j ) értéke soha nem j . Tehát f ( j , j ) értékét n - 1 -féleképpen választhatjuk ki. A keresett valószínűség tehát

( n - 1 ) n n n 2 - n n n 2

határértéke, ha n ? . Aki ismeri az e szám fogalmát, az azonnal látja, hogy ez a hatérérték 1 / e . Természetesen a bizonyítás nehézségét nem ez a lépés adja, hanem annak megmutatása, hogy a „jó” függvények közül választva már nagy valószínűséggel minden gép összerakható.

A következő feladatban azt vizsgáljuk, hogy mely gépek rakhatók össze ÉS és VAGY kapukból. Azt már láttuk, hogy nem az összes. Írjunk N helyett 0-t, az I helyett pedig 1-et, és vegyük észre, hogy e és v monoton függvények lesznek, azaz ha x 1 ? y 1 és x 2 ? y 2 , akkor e ( x 1 , x 2 ) ? e ( y 1 , y 2 ) és v ( x 1 , x 2 ) ? v ( y 1 , y 2 ) . Persze monoton függvényekből egymásba helyettesítés során újra és újra monoton függvényeket kapunk. Tehát újabb bizonyítást kaptunk arra, hogy a NEM kapu nem építhető meg. A monotonitás feltétele már jellemzi is a megépíthető gépeket.

2.6. Feladat. Igazoljuk, hogy ÉS- és VAGY-kapukból minden monoton gép összerakható.

Ha adott egy véges J jelhalmaz, és néhány (esetleg végtelen sok) fajta alkatrész, azaz a J -n értelmezett, véges sok változós függvények, akkor azoknak a függvényeknek a halmazát, amelyek ezekkel kifejezhetők, az adott függvények által generált klónnak nevezzük (lásd [1]). Klónt alkotnak például a monoton függvények a { 0 , 1 } halmazon. Kételemű jelhalmazon E. Post leírta az összes lehetséges klón szerkezetét, ennek az osztályozásnak a logikában van szerepe. Legalább háromelemű jelhalmazon ilyen leírás nem várható, mert itt már „ugyanannyi” klón van, ahány valós szám!

A téma zárásaként két megoldatlan problémát mutatunk be. Az elsőben olyan gépet próbálunk összerakni, mint amilyen például az x - y + z a számok között. Nevezzük az m háromváltozós függvényt Malcev-függvénynek, ha

m ( x , x , y ) = y = m ( y , x , x )

teljesül bármely x és y jelek esetén. (A Malcev-függvények azért fontosak, mert a jelenlétükben az adott klón sokkal „jobban” viselkedik, mint általában.) Egyáltalán nem triviális kérdés, hogy előre megadott függvényekből össze lehet-e állítani Malcev-függvényt, vagy sem. Például legyen a jelhalmaz { 0 , 1 , 2 } , és f az a kétváltozós függvény, amelyre f ( 1 , 1 ) = f ( 2 , 2 ) = 2 , f ( 0 , 0 ) = f ( 0 , 1 ) = f ( 1 , 0 ) = 0 , és a fennmaradó négy helyen az f értéke 1. Ekkor f példányaiból össze lehet ugyan rakni egy Malcev-függvényt, de csak nagyon bonyolultan. A nehézségek érzékeltetése végett megadjuk a „legegyszerűbb” Malcev-függvényt (a rövidség kedvéért f ( x , y ) helyett x y -t írva): m ( x , y , z ) = A ( B C ) , ahol

A = ( ( x y ) ( z ( ( x z ) ) ) ) , B = ( ( z ( x ( z z ) ) ) ( ( z ( x x ) ) ( ( x x ) ( x y ) ) ) ) , C = ( ( ( z ( x x ) ) ( ( x x ) ( z z ) ) ) ( ( ( x x ) ( z z ) ) ( ( y z ) ( z z ) ) ) ) .

2.7. Probléma. Adott egy véges jelhalmaz, és véges sok függvény. Van-e olyan „gyors” eljárás, ami eldönti, hogy összerakható-e ezekből egy Malcev-függvény?

(Az algoritmuselméletben többféle pontos jelentése is van a „gyors” szónak, itt „polinomidejű” eljárást értünk alatta). Ha az alkatrészek adottak, akkor ezek példányait végtelen sokféleképpen építhetjük össze, és elvileg minden így kapott függvényről meg kellene nézni, hogy Malcev-függvény-e. Nem nehéz belátni azonban, hogy egy Malcev-függvény létezésének kérdése véges sok lépésben mindig eldönthető, a fenti probléma tehát minden konkrét alkatrészhalmaz esetén elvben megoldható (csak esetleg lassan).

A második megoldatlan probléma azt firtatja, hogy lehetséges-e, hogy egy hasonló kérdés elvben sem oldható meg, azaz ugyanúgy eldönthetetlen, mint a szóprobléma. Ez Malcev-függvények helyett „majdnem” többségi függvényekről szól. Bemelegítésül lássuk be, hogy legalább háromelemű halmazon nem létezik „igazi” többségi függvény.

2.8. Feladat. Egy országban, ahol legalább hárman élnek, demokratikusan akarnak elnököt választani. Olyan eljárást szeretnének találni, hogy miután minden lakos leadta a szavazatát egy tetszőleges lakosra, ez az eljárás a szavazatokból automatikusan kiszámítja az elnök személyét. Az eljárás attól lenne demokratikus, hogy megkövetelik: ha mindenki megváltoztatja a szavazatát, akkor az elnök személye is mindenképpen változzon meg. Mutassuk meg, hogy ilyen eljárást csak úgy lehet csinálni, hogy kijelölünk egy diktátort, akinek a szavazata eldönti a leendő elnök személyét. (Ez nem azt jelenti, hogy az lesz az elnök, akire a diktátor szavaz, hanem azt, hogy bárki más bárhogy változtatja a szavazatát, az elnök személye ugyanaz marad.)

Nevezzük M -et „majdnem” többségi függvénynek, ha bármely x és y jelek esetén

M ( y , x , x , , x , x ) = M ( x , y , x , , x , x ) = = M ( x , x , x , , x , y ) = x .

2.9. Feladat. Ha a jelkészlet a valós számok halmaza, és alkatrészeink az x + y (kétváltozós), - x (egyváltozós) és x y (kétváltozós) függvényeknek felelnek meg, akkor lehet-e majdnem többségi függvényt készíteni?

2.10. Probléma. Adott egy véges jelhalmaz, és véges sok függvény. Van-e olyan (véges sok lépésből álló) eljárás, ami eldönti, hogy összerakható-e ezekből egy legalább háromváltozós majdnem többségi függvény?

Noha ez a kérdés megoldatlan, kapcsolatban áll egy másik, ehhez a témakörhöz tartozó logikai kérdéssel (Alfred Tarski úgynevezett véges bázis problémájával). Ez utóbbiról (aminek az ismertetésére itt nem vállalkozhatunk) Ralph McKenzie-nek sikerült megmutatnia (egy 120 oldalas bizonyításban), hogy eldönthetetlen, és az ott használt megoldási módszerrel sikerült részeredményeket elérnie a fenti problémában is. Erről a módszerről érdemes pár szót ejteni, mert ez a kulcsa például a szóproblémára vonatkozó eldönthetetlenségi eredmények bizonyításának is.

Ha írunk egy számítógépes programot, akkor azt szeretnénk, hogy ne legyen benne „végtelen ciklus”, azaz véges sok lépésben mindig megálljon. Ez annál nehezebb, minél bonyolultabb a program. Esetleg már annyira áttekinthetetlen, hogy felmerül az igény: nem lehetne-e számítógéppel ellenőriztetni, hogy el fog-e szállni, ha elindítjuk.

2.11. Kérdés. Lehet-e olyan DÖNT programot írni, amelyet ha elindítunk, és megadunk neki inputként egy tetszőleges programot (a forráskódját és az inputját), akkor azt beolvassa, és kiírja a MEGÁLL vagy az ELSZÁLL üzenetet aszerint, hogy ha a beolvasott programot elindítanánk, az megállna-e vagy sem?

A „program”-nak megfelelő precíz matematikai fogalom az úgynevezett Turing-gép. Ennek segítségével szabatosan meg lehet fogalmazni a fenti problémát, és belátni, hogy a válasz nemleges. Mi csak az ötletet érzékeltetjük. Tegyük fel, hogy letöltöttünk egy ilyen programot. Írjunk egy BOSZORKÁNY nevű programot. Ez három utasításból áll. Az elsőben meghívjuk a DÖNT programot, hogy olvassa be a BOSZORKÁNY programot. Ha az eredmény az, hogy ELSZÁLL, akkor megállítjuk a programot. Ha viszont az, hogy MEGÁLL, akkor végtelen ciklusba zavarjuk.

Kérdés, hogy ha a BOSZORKÁNY programot elindítjuk, akkor elszáll-e. Ha elszáll, akkor az első sorban az eredmény az, hogy ELSZÁLL, de akkor a programunk megáll, ez ellentmondás. Ha a BOSZORKÁNY program megáll, akkor az első sorban az eredmény az, hogy MEGÁLL, de akkor a programunk elszáll, ez is ellentmondás.

A véges bázis probléma megoldhatatlansága azon múlik, hogy az alkatrész-készletek olyan bonyolultak, hogy minden program modellezhető velük. Konkrétan McKenzie bizonyítása úgy halad, hogy minden lehetséges programhoz megad véges sok „alkatrészt”, méghozzá úgy, hogy ha a program megáll, akkor ezekre az alkatrészekre a véges bázis probléma teljesül, ha pedig a program elszáll, akkor a véges bázis probléma nem teljesül. Nyilvánvaló, hogy nem létezhet olyan program, ami a Tarski-problémát eldönti, hiszen akkor ez egy füst alatt eldöntené tetszőleges programról is, hogy megáll-e. Természetesen a bizonyítás nehézsége a részletekben van: az alkatrészek megtervezésében, és annak igazolásában, hogy a program akkor és csak akkor áll meg, ha a véges bázis probléma ezekre az alkatrészekre teljesül.