2. fejezet - Turing-gép

Az algoritmus fogalmának pontos megfogalmazá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 lambda-függvények, rekurzív függvények, Markov-gép és a Turing-gép. Ezek a fogalmak egyenrangúak egymással, egymásból kifejezhetők. A gyakorlatban leginkább a Turing-gép fogalma terjedt el. A Turing-gép több, egymással ekvivalens definíciójával is találkozhatunk különböző szakkönyvekben. Abban mindegyik definíció megegyezik, hogy a Turing-gépnek van egy központi vezérlőegysége, és egy vagy több szalag-egysége.

2.1. ábra - Turing gép modell

Turing gép modell

2.1. A Turing-gép felépítése

A szalagok négyzetekre, vagy más elnevezéssel mezőkre vannak osztva. Minden egyes mező maximum egy betűt vagy írásjelet tartalmazhat. Ezek a jelek egy előre rögzített, véges halmazból származnak. Ebben a halmazban van egy üres jelnek nevezett elem. A Turing-gép indulása előtt minden szalag minden egyes mezője —véges sok mezőtől eltekintve— ezt a jelet tartalmazza. Feltesszük, hogy minden egyes szalag (legalább) az egyik irányban végtelen. Minden egyes szalagegységhez tartozik egy-egy olvasó-író fej, amely minden egyes lépésben elolvassa a fej alatt álló mező tartalmát, azt törli, és egy jelet ír vissza (esetleg ugyanazt). Azt, hogy mit ír az adott mezőbe a fej, az olvasott jel és a vezérlő belső állapota határozza meg. Ugyanezek alapján a vezérlő új állapotba kerül és a fejet (más megfogalmazásban a szalagot) egy mezővel balra, jobbra mozgatja, vagy éppen helyben hagyja.

A vezérlő (legalább az) egyik állapota végállapot, s ha a gép ebbe kerül, akkor megáll. Az egyik kijelölt szalag üres jelektől különböző részét tekintjük a gép kimenetének (output). A vezérlő egy kijelölt állapotát kezdőállapotnak nevezzük, s a Turing-gép indulásakor a gép ebben az állapotban van.

Az egyszalagos Turing-gépet a (S, A,M, s0, F) ötössel írhatjuk le, ahol az S a vezérlő állapotainak halmaza, az A a mezőkre írható jelek halmaza, az s0 a kiinduló állapot, az F a végállapotok halmaza az M olyan satbl ötösök halmaza, ahol s és t a vezérlő állapotai, a és b egy-egy karakter (betű vagy írásjel), l pedig a L,R,S betűk valamelyike, melyek rendre a balra, jobbra mozgást, illetve helybenmaradást jelzik. (Az n-szalagos Turing-gép esetén az M 2 + 3n-esek halmaza lesz, minden szalag esetén külön-külön meg kell adni, hogy mi kerül az adott szalagra, és a szalag merre mozdul.) Ha az (S, A,M, s0, F) Turing-gépben az M ötöseiben a harmadik, negyedik és ötödik értéket az első kettő egyértelműen meghatározza, azaz a harmadik, negyedik és ötödik érték az első kettőnek függvénye, akkor determinisztikus Turing-gépről beszélünk, ellenkező esetben nemdeterminisztikus Turing-gépről.

2.1. példa - 3. példa

A hárommal osztható hosszúságú egyesekből álló szavakat elfogadó egyszalagos, determinisztikus Turing-gép a következő:

S = {q0, q1, q2, qv}

A = {0, 1}

s0 = q0

F = {qv}

M = {q01→q11R, q11→q21R, q21→q01R, q00→qv0S, q10→q10S, q20→q20S}

Vannak akik jobban szeretik a Turing gép következő ábrázolását:

2.1. táblázat -

 01
q0 qv0Sq11R
q1 q10Sq21R
q2 q20Sq01R
qv   


Lássuk e Turing-gép futását pár bemenetre! Az egyszerűbb jelölés kedvéért csupán a szalag aktuális tartalmát írjuk le, s a fejet a soron következő karakter előtt található állapot fogja jelölni. Ennek megfelelően az 11 input esetén a következő a gép kezdeti konfigurációja: ...0q0110....

  1. ...0q0110...

  2. ...01q110...

  3. ...011q20...

  4. ...

  5. ..011q20...

  6. ...

Mint a táblázatból lehet látni, az 11 input esetén a második lépestől kezdődően a Turing-gép nem vált állapotot, s így végtelen ciklusba kerül.

Az 111 input esetén a negyedik lépésben a Turing-gép végállapotba kerül, s így megáll.

  1. ...0q01110...

  2. ...01q1110...

  3. ...011q210...

  4. ...0111q00...

  5. ...0111qv0...


Szokás ilyenkor azt mondani, hogy az adott Turing-gép elfogadta ezt az inputot. A Turing-gépeket felhasználhatjuk függvények kiszámolására, azaz az argumentumokat a bemeneti szalagra írva, a gépet elindítva a Turing-gép a kimeneti szalagra a függvény végeredményét írva megáll.

Felhasználhatjuk a Turing-gépeket nyelvek felismerésére is. Szavaknak nevezzük az A ábécé betűiből alkotott véges sorozatokat. Nyelvnek nevezzük szavak egy halmazát. A T Turing-gép által felismert LT nyelv pontosan azokból a szavakból áll, melyekkel mint bemenettel indítva a Turing-gép megáll.

Egy L nyelvet rekurzívan felsorolhatónak nevezünk, ha van olyan Turing-gép amely által felismert nyelv éppen az L. Egy L nyelv rekurzív, ha létezik olyan Turing-gép, mely tetszőleges inputra megáll, és a szóhoz tartozó végállapot pontosan akkor egyezik meg az egyik előre kijelölt állapottal, ha a szó L-beli. Az f függvény parciálisan rekurzív, ha létezik olyan Turing-gép, amely kiszámolja. Az f függvény rekurzív, ha létezik olyan Turing-gép, amely kiszámolja; és az output minden bemenetre definiálva van.