Chapter 4. A Turing-gép

Az algoritmus fogalmáról az informatikával szorosabb kapcsolatot ápolóknak van valamilyen elképzelése. A legtöbb esetben meg tudjuk mondani, hogy az éppen vizsgált dolog algoritmus-e vagy sem. Legalábbis a "hétköznapi" esetekben. Sokan asszociálnak az algoritmusok kapcsán számítógép-programokra, nem teljesen alaptalanul. Nem egyértelmű azonban, hogy például egy orvosi vizsgálat, vagy akár a járás tekinthető-e algoritmusnak.

Minél inkább próbáljuk pontosítani a fogalmat, annál inkább ütközünk korlátokba. Az algoritmusokkal kapcsolatban a következő elvárásaink vannak:

Az algoritmusnak jól meghatározott feladatot illetve feladattípust kell megoldania.

Az algoritmus elkülöníthető lépésekből álljon, ezen lépések száma (típusa) véges legyen. Szeretnénk a feladatra adott megoldást véges időben megkapni.

Az algoritmus minden egyes lépésének pontosan definiáltnak kell lennie.

Az algoritmus számára szükség lehet bizonyos bemenő adatokra, amivel a megoldandó feladatosztály egy speciális feladatát jelöljük ki. Az adatok mennyisége csak véges lehet, annak minden értelmében.

Az algoritmus válaszoljon a bemenetre. A válasznak megfelelően értelmezhetőnek és természetesen végesnek kell lennie.

Látható, hogy ha megfelelően általánosan akarjuk meghatározni az algoritmus fogalmát, akkor több bizonytalanságot kell hagynunk benne. A legproblémásabb rész a "lépés" fogalma. Mit jelent az, hogy "pontosan definiált"? Ha megadunk egy igazán pontos definíciót, máris leszűkítjük a lehetőségeinket.

Az algoritmus mibenlétének pontos meghatározásával a múlt század első felében többen is próbálkoztak. Ennek eredményeképpen több, egymástól különböző fogalom is megszületett, mint például a függvények, rekurzív függvények, Markov-gép és a Turing-gép. Mivel ezek pontosan definiált modellek, az az érzésünk lehet, hogy nem tekinthetők teljes mértékben alkalmasnak az algoritmus fogalmának helyettesítésre.

Belátható, hogy az előbb felsorolt modellek egymással ekvivalensek, ami azt jelenti, hogy minden feladat, ami az egyik modellben megoldható, megoldható a másikban is.

Az algoritmus fogalmának helyettesítésére azonban mind a mai napig nem találtak a felsoroltaknál teljesebb modellt. A jegyzetben a legnagyobb figyelmet a Turing-gép modelljének fogjuk szentelni, mivel az egyik leginkább letisztult, világosan érthető és sok szempontból kifejező fogalomnak bizonyult. Igaz ez annak ellenére is, hogy a ma legszéleskörűbben elterjedt számítógép-architektúrák modellezésére nem kifejezetten alkalmas.

Turing-gépek segítségével könnyen ki tudjuk fejezni a kiszámíthatóság, azaz az algoritmussal való megoldhatóság fogalmát, és meg tudunk határozni egy precíz mértéket az algoritmusok bonyolultságának valamint a feladatok nehézségének leírására is.

A Turing-gép elnevezés a modell kitalálójára, Alan Turingra (1912-1954) utal. A tényleges definíciónak számtalan azonos értelmű változata létezik. Ezek közül mi az egyik leginkább letisztult, megfelelően kifejező változatot használjuk.

Ahhoz, hogy egyáltalán megpróbálhassuk matematikai eszközökkel leírni az algoritmusokat, szűkíteni kell a megoldásra váró feladatok körét. Ki kell zárnunk a lehetőségek közül többek között a fizikai objektumokon végrehajtott mechanikai műveleteket. Ez nem jelenti azt, hogy az ilyen jellegű problémákat nem tekintjük algoritmikusan megoldhatónak, csak annyi, hogy a fizikai algoritmus helyett annak egy matematikai modelljét tudjuk csak kezelni, és egy megfelelő interfész segítségével fizikai műveletekké alakítani. Ez lényegében a gyakorlatban minden esetben így működik, hiszen önmagukban a végrehajtott algoritmusaink, illetve a nekik megfelelő programjaink eredményeit nem észlelhetnénk.

Feltételezzük tehát, hogy a feladat és annak paraméterei, bemenő adatai valamilyen véges reprezentációval leírhatóak. Ennek megfelelően a továbbiakban az algoritmusaink bemenetét (a feladat leírását) egy rögzített véges ábécé feletti szóként adjuk meg, és hasonló formában várjuk a választ is. Egy algoritmust tekinthetünk tehát úgy, mint egy leképezést, amely szavakhoz szavakat rendel. Világos, hogy meg tudunk adni olyan algoritmusokat, amelyek bizonyos bemenetekre "nem reagálnak", azaz nem adnak kimenetet (ilyenkor parciális függvényt valósítanak meg). Elképzelhetőek olyan speciális algoritmusok is, amelyek a bemenő szavak végtelen számossága ellenére csak véges sok lehetséges választ adhatnak. Erre példa a klasszikus elfogadó (felismerő) algoritmus, amely a bemenet értékétől függően igennel vagy nemmel válaszol (elfogadja, illetve elutasítja a bemenetet).

4.1. Definíció

Legyen  egy ábécé,  egy nyelv,  és  egy 
transzformáció.
Algoritmikus feladatnak (vagy egyszerűen csak feladatnak)nevezzük a 
következőket:
1. Határozzuk meg, hogy fennáll-e a  reláció!
2. Határozzuk meg  értékét!

Az 1. típusú feladatot döntési (felismerési) feladatnak, 
míg a 2. típusút transzformációs feladatnak nevezzük.

A későbbiekben látni fogjuk, hogy már az előbb említett, egyszerűnek látszó döntési feladat sem könnyű. Bebizonyítjuk, hogy vannak olyan problémák, amelyekről nem tudjuk eldönteni még azt sem, hogy egyáltalán megoldhatóak-e.

Figure 4.1. Turing gép modell

Turing gép modell

4.1. A Turing-gép definíciója

4.2. Definíció

A  ötöst Turing-gépnek nevezzük, ha
: véges, nem üres halmaz; állapotok halmaza

              véges, legalább  elemű halmaz, ; szalag ábécé

            ; kezdő állapot

            , nem üres; végállapotok halmaza

            ; átmenetfüggvény
         

A fenti formális definíciót megfelelő értelmezéssel kell ellátnunk. A szemünk előtt a következő "fizikai" modell fog lebegni:

A Turing-gép három fő részből áll:

1. egy mindkét irányban végtelen szalag, cellákra osztva, a cellák tartalma a ábécé elemei közül kerül ki;

a szalagon legfeljebb véges sok cellában van -beli elem és ezek között nem lehet (összefüggően helyezkednek el az értékes jelek);

2. egy regiszter, -beli értéket tartalmaz, ez határozza meg a Turing-gép pillanatnyi működését;

3. egy író-olvasó fej, ami mindig egy konkrét cellára mutat; ez kapcsolja össze a szalagot a regiszterrel.

A Turing-gép egy lépése során beolvassa a szalagról az író-olvasó fej alatt levő jelet, a beolvasott jel értékétől, és a regiszterben tárolt állapottól függően a által meghatározott módon lép:

- visszaír egy jelet az író-olvasó fej alatti cellába és megváltoztatja az állapotát vagy

- a szomszédos cellák valamelyikére mozdítja az író-olvasó fejet és megváltoztatja az állapotát.

A Turing-gép alternatív meghatározásaiban általában egyidejűleg történik a szalagra írás és fejmozgatás, a szétválasztás segítségével azonban bizonyos definíciókat lényegesen egyszerűbben és letisztultabban adhatunk meg.

A szem előtt tartott értelmezésnek megfelelően szükség van matematikailag is pontos, jól meghatározott "működésre". Ezt írjuk le a következő definíciókkal.

4.3. Definíció

A  Turing-gép egy konfigurációja 
            
(= regiszterállapot + szalagtartalom, az író-olvasó fej helyének 
jelölésével)

4.4. Megjegyzés

Egy  Turing-gépnek csak akkor létezik  alakú konfigurációja,
ha  vagy .

4.5. Definíció

Azt mondjuk, hogy a  Turing-gép. egy lépésben (vagy közvetlenül) 
átmegy 
            -ból a  konfigurációba (jelekben ), ha
   
   
            
és a következők közül pontosan egy teljesül:
1) 
   
            
   
            , ahol  , és .
   --- felülírási üzemmód
2) 
   
            
   
            , ahol  ,  és .
   --- jobbra lépési üzemmód
3) 
   
            
   
            , ahol  ,  és .
   --- balra lépési üzemmód

4.6. Megjegyzés

1. Mivel  minden  és a   esetén egyértelműen definiált, 
   ezért minden szabályos konfiguráció esetén vagy létezik egyértelműen
    konfiguráció, amelyikbe közvetlenül átmegy, vagy egyáltalán nem 
   létezik ilyen.
2. A Turing-gép konfigurációjának definíciója, illetve a definíció 
   utáni megjegyzés alapján, ha  és , akkor a 
   Turing-gép csak akkor tud továbblépni, ha  vagy .
3. A  jel tulajdonságai alapján, ha  és ,
   a  átmenetben .
   Hasonlóképpen, ha  és , akkor a  átmenetben
   
            .

4.7. Definíció

A  Turing-gép egy számítása konfigurációk egy  sorozata
  amelyekre

1. , ahol ;
2. , ha létezik -ből közvetlenül elérhető konfiguráció (és ez 
   az egyértelműség miatt );
3. , ha nem létezik -ből közvetlenül elérhető konfiguráció.

A  szót a  
               bemenetének nevezzük.

Ha  olyan, hogy , akkor azt mondjuk, hogy a számítás 
véges, a Turing-gép a  végállapotban megáll. Ekkor a  szót
 
               kimenetének nevezzük.

Jelölése: .

Ha egy  esetén a  Turing-gépnek végtelen számítása van, akkor 
nem értelmezünk kimenetet.  Jelekben:  . (Nem összetévesztendő 
a 
               kimenettel.)

4.8. Megjegyzés

Egy  Turing-gépnek kétféleképpen lehet végtelen számítása egy  
bemeneten:
1. -re létezik -ből közvetlenül elérhető konfiguráció;
2. , amelyikre -ből nincs közvetlenül elérhető konfiguráció és
   -hez tartozó állapot nem végállapot. (A Turing-gép "befagy" a 
    konfigurációban.)