1. fejezet - A hagyományos számítási modell

Mielőtt belekezdenénk a nemhagyományos számítások elméletébe, tekintsük át a hagyományosnak, illetve klasszikusnak nevezett számítástechnika néhány alapvető jellemzőjét.

Elsőként a Turing-géppel és a kiszámíthatóság fogalmának átismétlésével kezdünk. Ezt Alan Turing 1936-ban vezette be bizonyos automatikusan végrehajtható számítási eljárások tanulmányozására. Egyszerűsége ellenére a modell jól használható a hagyományos elektronikus számítógépek számítási kapacitásának elvi korlátainak kutatásában.

1.1. A Turing-gép

A Turing-gép egy absztrakt „szekvenciális hozzáférésű” számítási modell amit a számítástudomány ma is használ, és amely például a Dömösi Pál, Falucskai János, Horváth Géza, Mecsei Zoltán, Nagy Benedek: Formális Nyelvek és Automaták, Debrecen, 2011 (Kelet-Magyarországi Tananyagtárház) jegyzetben is részletesen be van mutatva, most innen vesszük át e modell leírását.

A Turing-gép egy potenciálisan végtelen szalagmemóriával és egy író-olvasó fejjel ellátott véges állapothalmazzal rendelkező automata. A szalagmemória pozíciókra van osztva, s minden egyes pozíció mint memóriaegység az úgynevezett szalagábécé pontosan egy betűjének tárolására képes. Kezdetben a Turing-gép egy előre specifikált kezdőállapotában van, s a szalagon egy véges hosszúságú input szó helyezkedik el. A Turing-gép szekvenciális működésű: működésének kezdetekor a Turing-gép író-olvasó feje az input szó első betűjén áll. Az input szó előtti és utáni (végtelen sok) szalagpozíció egy speciális betűvel, a szóközzel (üres betűvel) van feltöltve. Hogy az input szó elkülöníthető lehessen a szalag többi részén tárolt mindkét irányban végtelen számú szóköztől, feltételezzük, hogy az input szó nem tartalmaz szóközt. Az input szó tehát az író-olvasó fej alatti betűtől (jobbra haladva) tart a szalag utolsó nem üres betűjéig. Speciálisan, üres input szó is elképzelhető. Ez esetben a szalag minden egyes pozíciója szóközzel van feltöltve, és az író-olvasó fej ezek egyikére mutat. (Utolsó szóköztől különböző betű pedig ekkor értelemszerűen nincs.) A Turing-gép diszkrét időskála mentén, elkülönített időpillanatokban hajt végre egy-egy elemi műveletet, mely az író-olvasó fej alatti betű olvasásából, ezen betű felülírásából, a belső állapot változtatásából, s az író-olvasó fej egy pozícióval való balra avagy jobbra mozgatásából, vagy éppen a fej helybenhagyásából áll. Amennyiben a Turing-gép eljut egy végállapotba, megáll. A gépet úgy is elképzelhetjük, hogy nem a fej lépked a szalagon, hanem a gép képes rá, hogy a végtelen hosszúnak tekintett szalagot mozgassa előre-hátra, mindig egy-egy pozícióval. A gép a szalagról olvashat, és arra írhat is. A Turing-gép szalagja végtelen, s mivel ezt bármely irányban mozgatni tudja, a gép (külső-)memóriája végtelennek tekinthető (1.1. ábra).

1.1. ábra - A Turing-gép rajza.

A Turing-gép rajza.

A következő definíció a Turing-gép formális matematikai megfogalmazása.

A rendezett hetest Turing-gépnek nevezzük, ahol

  • a belső állapotok véges halmaza;

  • az input ábécé, az input pedig valamely szó;

  • a szalagjelek véges halmaza, , ezek mind az input, mind az output, illetve a részeredmények megadására szolgáló jelek beleértve a szóköz betűt is, viszont ;

  • kezdőállapot;

  • a végállapotok halmaza;

  • a gép átmenet-, vagy mozgásfüggvénye.

A fent ismertetett modell a determinisztikus Turing-gép. A Turing-gép nemdeterminisztikus változata is széleskörben ismert, az egyedüli különbség, a definíciót tekintve, mozgásfüggvényben van, annak alakja ezesetben , vagyis a halmazból a halmaz lehetséges részhalmazaiba képez.

Eredetileg a Turing-gép a állapotban van, és az író-olvasó feje a bemeneti szó első betűjére mutat (vagyis a szalag legbaloldalibb nem elemére), ezt hívjuk az inputhoz tartozó kiindulási konfigurációnak. A Turing-gép működése a következő:

Ha tehát a Turing-gép egy állapotban van és az író-olvasó fej alatt valamely jel áll, akkor a hármas szolgáltatja a gépnek a műveleti lépés végrehajtása utáni új állapotát, az szalagjelet felülíró szimbólumot (mely nem feltétlen különböző a felülírt szimbólumtól), illetve az elmozdulás irányát. Az a következőt jelenti: esetén a Turing-gép író-olvasó feje egyet balra lép, azaz a szalagot a gép egy pozícióval jobbra húzza; esetén a gép feje egyet jobbra lép, azaz a szalagot balra húzza; esetén pedig a szalagot nem mozdítja, a gép olvasó-író feje és a szalag helyben marad.

A nemdeterminisztikus esetben a -beli rendezett hármasok egyike szolgáltatja (bármelyike szolgáltathatja) az új állapotot, az új szalagjelet, illetve a mozgás irányát.

Abban az esetben, ha , azt úgy interpretáljuk, hogy ha a gép a állapotban az író-olvasó fej alatt az betűt találja, további működését felfüggeszti (megáll). Eredményt viszont csak akkor szolgáltat, ha végállapotban áll meg a gép (ezt hívjuk végkonfigurációnak).

Megjegyezzük, hogy bár a gép szalagját mindkét irányban végtelennek tekintjük, minden időpillanatban csak véges sok -tól különböző jel lehet rajta.

Tekintsük először a determinisztikus Turing-gépeket; ezeknek is számos változata ismert. Például, az egyszerűbb leírás kedvéért sokszor többszalagos Turing-gépet használunk:

A egy -szalagos Turing-gép, ahol

természetes szám, ennyi szalagja van a Turing-gépnek;

és csupán a mozgásfüggvény különbözik attól, mint amit az egyszalagos esetben megadtunk:

a -szalagos Turing-gép átmenetfüggvénye: .

Működését tekintve a többszalagos Turing-gép egy lépésben olvas/ír egyszerre több szalagra is. Kezdőkonfigurációban az első szalagon (ez az inputszalag) van a feldolgozandó adat, a többi szalag pedig üres. Ezek a gépek az inputszalagot csak olvasni tudják, azt nem írják át. Kettőnél többszalagos gépek esetén szokás az utolsó szalagot az outputnak fenntartani, ekkor a számítás végén azon a szalagon olvasható az eredmény, általában ez a szalag ilyenkor csak írható, és csak jobbra lépked rajta az írófej.

Minden többszalagos Turing-gép működése szimulálható egyszalagos Turing-géppel, vagyis egyszalagos Turing-gép is el tudja végezni azt a számítást, amit egy többszalagos Turing-gép. Ezt úgy lehet belátni, hogy egyszalagos Turing-géppel szimuláljuk a többszalagos működését. A szalagokat összeragasztjuk és speciális jelekkel jelöljük, hogy a szimulálandó automata melyik feje hol tart (lásd az 1.2. ábrát). A új gép összegyűjti ezeket az információkat a véges állapothalmazba kódolva, és visszalépked a megfelelő pozíciókba, hogy a megfelelő lépés szimulációját elvégezze.

1.2. ábra - Többszalagos Turing-gép szimulációja egy szalaggal, összetett ábécé szimbólumokkal.

Többszalagos Turing-gép szimulációja egy szalaggal, összetett ábécé szimbólumokkal.

Megadhatunk olyan Turing-gép változatot, ahol a fej csak a és irányokba léphet, és nem maradhat . Belátható, hogy egy ilyen Turing-gép szimulálni tudja az eddigiekben ismertetett változatnak a fejet helyben hagyó lépéseit is: pl. egyet balra lép a fej, és egy olyan állapotba kerül az automata, amiben bármit is olvas a szalagon, azt nem változtatja meg, viszont jobbra visszalép és az eredeti automata állapotának megfelelő állapotba kerül.

Ugyancsak szokásos a csak egyirányban végtelen szalagú Turing-gép használata, amelyik szintén képes az általános változat szimulációjára. Ekkor a szalag első karaktere egy speciális jel, amiből a gép rájön, hogy erre nem mehet tovább a fej. Ekkor egy olyan speciális állapotba kerül, aminek hatására jobbra lép, először leírja azt a jelet, ami eredetileg a speciális szimbólum helyére írt volna (ha a szalag mindkét irányban végtelen lenne), majd az itt olvasott karaktert eggyel jobbra, és így tovább, vagyis a szalag teljes (értelmes) tartalmát eggyel jobbra másolja, ezután (észlelve a felhasznált tárterület jobb szélét), a fej vissza mozog a baloldalra, ahol a gép folytatja az eredetileg tervezett számítását.

Megkülönböztethetünk kiszámító és eldöntő Turing-gépeket a következő definíció alapján.

Amennyiben a Turing-gép célja adott függvény kiszámítása a megadott bemenő értékekkel, akkor a gép a megállásakor az (output)szalagon a megfelelő eredményt hagyja. Ezzel szemben vannak olyan számítások, amikor a választ egy igen-nem kérdésre keressük, ezesetben eldöntő Turing-gépről beszélünk. Az eldöntő Turing-gépekkel lehet pl. egy nyelvet elfogadtatni a következőképpen: bemenet egy szó, a Turing-gép számításának eredménye pontosan akkor „igen” ha teljesül. (Hasonló módon szokás azokat az input szavakat elfogadni, amelyekre a számításokat az elfogadó állapotban fejezi be a gép.)

A Church-Turing tézis értelmében egy igen/nem problémaosztályt megoldhatónak hívjuk, ha létezik olyan rögzített algoritmus (Turing-gép), mely az osztály tetszőleges problémája mint bemenő adat esetén eredményként megadja a helyes „igen” vagy „nem” választ. 1936-ban Turing azt az akkor meglepő eredményt kapta, hogy létezik ebben az értelemben megoldhatatlan feladatosztály.

A kiszámíthatóság fogalma a számítástudományban másként is megjelenik: a Turing-gépekkel elfogadott nyelvek osztálya éppen a rekurzívan felsorolható nyelvek osztályával egyezik meg. Ugyanezt a nyelvosztályt lehet generálni a Chomsky-féle generatív nyelvtanokkal (0-típusú nyelvtanok). A Turing-gép fogalma tehát szorosan összekapcsolódik a „kiszámíthatóság” fogalmával. Turing-géppel mindent (és pont azokat a feladatokat) ki lehet számolni, amit algoritmikusan meg lehet oldani. Ezek szerint a Turing-gép a lehető legáltalánosabb számítási eszköz, azaz minden, ami effektíve kiszámítható, kiszámítható Turing-géppel is.

Akkor mondjuk, hogy egy Turing-gép valamely input szó hatására megáll (és eredményt szolgáltat), ha az input szó eleme a tekintett Turing-gép által felismert nyelvnek (elfogadó Turing-gép esetén, vagy általában, ha) az input szóhoz tartozó kezdő konfigurációból kiindulva a gép eljut egy végkonfigurációba.

A Turing-gépek megállási problémája a következő: van-e algoritmus arra, hogy eldöntsük, hogy egy tetszőlegesen adott Turing-gép egy tetszőlegesen adott input szóra megáll-e. Turing tétele értelmében ez a probléma megoldhatatlan. Ez tulajdonképpen azt jelenti, hogy vannak olyan jól megfogalmazható problémák, amiknek elvileg sincs (algoritmikus) megoldása.

Szerencsére azonban rengeteg olyan probléma ismert, ami megoldható. Ezekkel kapcsolatban a következő fontos kérdés, hogy milyen hatékonyan oldhatóak meg. Ezekkel a problémákkal foglalkozik a bonyolultságelmélet, amit a fejezet végén levő alfejezetben tekintünk át röviden.

Most viszont egy speciális típusú Turing-gépet fogunk tekinteni, aminek létezése nagyban hozzájárult az általános célú számítógépek megjelenéséhez.

1.1.1. Univerzális Turing-gép

Ebben a részben a Turing-gépek speciális fajtájával, az ún. univerzális Turing-géppel fogunk foglalkozni.

Az univerzális Turing-gép többféleképpen is megadható, mi itt most az egyik ilyen megvalósítással fogunk foglalkozni.

Az Turing-gépet univerzálisnak nevezzük a Turing-gépek osztályára nézve, ha minden Turing-géphez van olyan hogy minden -ra a futásának eredménye az inputon megegyezik az futásának eredményével a inputon (ahol speciális elválasztó szimbólum).

A „programja” (az nyelvén), pedig egy tetszőleges (input) szó. Ha az inputot kapja, akkor ugyanazt csinálja, mint a programmal az -en.

Az univerzális Turing-gép tulajdonképpen egy általános elvont számítógép, ami minden Turing-gépet képes szimulálni, vagyis elvileg a programjának megfelelően képes feldolgozni az input szót. Ez azt jelenti, hogy van olyan gép, ami minden kiszámítható függvényt ki tud számolni.

Az alábbiakban egy példát adunk az univerzális Turing-gépre.

Tulajdonképpen a átmenetfüggvényt kell megadnunk ami a véges értelmezési tartományon és a véges értékkészleten van értelmezve, illetve a másik Turing-gép ( ) leírásának (program) kódolását.

Legyen valamilyen Turing-gép, melynek darab belső állapota van, és a szalagábécéje betűt tartalmaz. Tegyük fel, hogy -et kódolt formában adtuk meg (jelöljük -mel ezt a leírást). A továbbiakban vázlatosan ismertetjük, hogy hogyan tudjuk modellezni működését az univerzális Turing-géppel. Tegyük fel, hogy a inputon dolgozik, aminek kódja . Először azt kell megadnunk, hogy adott és esetén ezeket az információkat miképpen tároljuk az szalagján (azaz mi lesz kezdőkonfigurációja), majd pedig azt, hogy ezek hatására hogyan fog működni.

Jelöljünk ki a szalagon egy mezőt, és írjunk ebbe a mezőbe a rögzített elválasztójelet a szalagábécéből. A szalagnak a kiválasztott mezőtől jobbra eső felét három részre osztjuk. Az első részt nevezzük pufferterületnek; ez közvetlenül az jel után kezdődik, legalább mezőt tartalmaz, és ezek mindegyikébe van írva. A pufferterülettől jobbra eső szalagrész legelső mezőjébe egy jelet teszünk a szalagábécéből, utána beírjuk kódolt formáját, -et, három -t téve a végére. A szalagnak ezen részét nevezzük a kódolási területének. A harmadik rész a második résztől jobbra helyezkedik el. Az első mezőjébe egy rögzített jelet írunk, majd a bemeneti szó kódolása következik. A szalagnak e három részen kívül eső mezői (kezdetben) üresek.

A pufferterület arra szolgál, hogy mialatt a valamelyik lépését szimuláljuk, ide másolhassuk a pillanatnyi belső állapotának, illetve az éppen leolvasott -beli szalagjelnek a kódját. Az jel általában az előtt a rendezett ötös előtt fog állni, amely azt határozza meg, hogy milyen belső állapotban van a gép, milyen szalagjelet olvasunk éppen, mivel kell ezeket kicserélni (új állapot és új szalagjel), s eközben milyen irányban mozduljon el a olvasófeje a szalagon. A jel a szalagjára felírt jelek közül jelöli ki azt, amelyiket éppen olvasunk.

Az -ben lezajló számítási folyamatot, mellyel a Turing-gép működését szimuláljuk a bemeneti szóval, olyan szakaszokra bonthatjuk, melyek sorra megfelelnek a egyes konfigurációi közötti átmeneteknek.

Az működésének egy ilyen szakasza az alábbi módon zajlik le. Az univerzális Turing-gép először a pufferterület elejére másolja azt az 1-esekből álló blokkot, amely közvetlenül az jel után következik – nevezzük ezt a maximális hosszúságú, csak 1-eseket tartalmazó szót -blokknak –, majd a végére odaír még egy jelet. Ezután kitörli -t, és jobbra haladva megkeresi a -t tartalmazó mezőt. Amikor ezt megtalálta, akkor a után következő 1-esekből álló blokkot ( -blokkot) is átmásolja a pufferterületre az előbb beírt második jel után, majd visszaírja -t a kódolt leírása, elé. Így a pufferterületre az aktuális belső állapot és a szalagról éppen beolvasott jel kódja került. A következő lépésekben az jel után következő két 1-es blokkot hasonlítja össze a pufferterületen levőkkel. Ezáltal azt ellenőrzi, hogy a gép soron következő konfigurációátmenetét az a rendezett ötös határozza-e meg, amelynek kódja az jel után van leírva. Ha a blokkok megegyeznek, ez azt jelenti, hogy megtaláltuk a keresett ötöst. Ha nem, akkor áthelyezi az jelet a következő rendezett ötös kódolása elé, majd újrakezdi a blokkok összehasonlítását. Abban az esetben, ha a leírásában szereplő ötösök közül egyik sem felel meg, leáll a működésével (az eredeti is ugyanezt tenné a inputra). Ha viszont megtaláljuk a keresett ötöst, akkor kitörli a pufferterületet, majd az jelet átteszi az ötösben szereplő harmadik elem elé. Ezután kicseréli a után következő blokkot az utáni blokkal, majd -t jobbra mozdítja el a rendezett ötös negyedik elem elé. Miután leolvasta ezt a negyedik elemet is, mely a olvasófejének elmozdulási irányát határozza meg, átteszi a jelet az elem mögé, az ötödik elem elé. Attól függően, hogy a negyedik blokkban két vagy csak egy darab 1-est talált-e, az egy blokkal jobbra vagy egy blokkal balra tolja el -t. Ha eredetileg a szalagszó bal szélén volt, és -nek balra kellett lépnie, akkor a szó kódolását jobbra tolja, és egy üres mező kódjelét írja be a után. Ha pedig a szalagszó jobb szélén állt, s jobbra kellene elmozgatni, akkor a szó végére írja egy üres mező kódját. Amikor tehát mindezzel végeztünk, az jel után álló 1-es blokk a aktuális belső állapotát jelzi, a utáni blokk pedig azt a szalagjelet, amelyet -nek a következő lépésben be kellene olvasnia. Minden készen áll tehát arra, hogy a következő lépését szimuláló szakasz megkezdődhessen.

Az működésének egyes szakaszai így egy-egy lépését modellezik. ezeken kívül még a következőket hajtja végre: a munka legelején a szalag mindhárom részében a -kat a saját üres-jeleire cseréli, a munka végeztével pedig, olyankor, amikor leállna, még ellenőrzi, hogy -nek végállapota-e az az állapot, amelyben megállt, és ettől függően kerül saját maga is végállapotba, ill. nem végállapotba.

Minden Turing-gép működése szimulálható olyan Turing-géppel, amiben a szalagábécé bináris, vagyis .

Az Univerzális Turing-gép létezése azt mutatja, hogy elvileg konstruálható olyan számítási eszköz, amely programozható és mindent ki tud számítani, ami kiszámítható. A gyakorlati megvalósulás felé a következő lépés a Neumann elv, amit a következő fejezetben ismétlünk át.

Az absztrakt számítógép után lássuk a valódi gépek milyen elven működnek.