A Turing-gép architektúrája

Megjegyzés: A Turing-gépnek több "változata" is létezik a szakirodalomban (pl. balról is végtelen szalag, ún. "igen" és "nem" típusú elfogadó, ill. elutasító megállási állapotok a halt vagy stop állapot mellett, stb.). A különbözőképpen definiált Turing-gépek azonban ekvivalensek egymással.

A Turing-gép egy végletekig leegyszerűsített számítógép elméleti modelljének tekinthető, amellyel egyszerűsége ellenére minden adatfeldolgozási algoritmus leírható. Ezt fejezi ki az ún. Church-tézis.

Church-tézis (1936)

Minden intuitív értelemben kiszámíthatónak tekinthető (azaz algoritmizálható) függvényt ki lehet számítani a Turing-géppel.

A Turing-gép részei:

(1) egy jobbra végtelen hosszúságú szalag, a Turing-gép memóriája, amely cellákból (vagy rekeszekből) áll

• minden cella egy karaktert tartalmaz a Turing-gép ábécéjéből, amely pl. a {>,0,1,_} karakterekből állhat:
  • a bal szélső cella a start karaktert vagy szimbólumot (>) tartalmazza
  • ez az első karakter, amit az író-olvasó fej be fog olvasni
  • a start karaktert beolvasása után az író-olvasó fej mindig visszaírja (azaz nem cseréli ki más karakterre)
  • a start karakter beolvasása után az író-olvasó fej mindig jobbra fog lépni (azaz nem "lép le" balról a szalagról)
  • bináris ábécéjű Turing-gép esetén a további cellákban bináris számjegyek (0 vagy 1) szerepelhetnek (ill. az ezeket elválasztó üres karakter, ld. alább)
  • a nem használt cellák az üres karakterrel (_) vannak feltöltve
• a szalag tartalmazza
• a gép indulásakor a Turing-gép inputját
• a gép működése közben a képződött részeredményeket
• a gép leállása után a Turing-gép outputját
• a szalagon levő adatok a Turing-gép működését is vezérlik (azaz a Turing-gépben az adatok és a gépet működtető program nem választható élesen szét; a memória a gép indulásakor a bemeneti, input egység, a gép megállásakor a kimeneti, output egység funkcióját is ellátja)

(2) egy író-olvasó fej, amely minden lépésben

• beolvas egy karaktert a szalagról, és továbbítja a vezérlő egységnek
• kiírja a vezérlő egységtől kapott egy karaktert a szalagra
• a vezérlő egység által küldött parancsnak megfelelően
  • elmozdul egy cellával jobbra,
  • elmozdul egy cellával balra, vagy
  • helyben marad

(3) egy állapotregiszter (R), amely a Turing-gép aktuális állapotát tárolja (induláskor az ún. kezdőállapotot)

• a Turing-gép lehetséges állapotainak halmazát a Turing-gép alapprogramja tartalmazza
• az állapotok egyfajta "címke" funkciót látnak el, azaz az utasítások egy csoportját adják meg
• minden utasítás megadja, mi lesz a Turing-gép következő állapota

(4) egy (központi) vezérlő egység (KVE), amely tárolja és lépésenként végrehajtja a Turing-gép alapprogramját (vezérli a Turing-gép utasításciklusát)

• a Turing-gép alapprogramját egy olyan táblázat adja meg, amely a Turing-gép állapotai (a táblázat sorai) és a Turing-gép ábécéje (a táblázat oszlopai) függvényében tartalmazza a Turing-gép utasításait

A vezérlő egység minden lépésben az író-olvasó fej által beolvasott karakternek és az állapotregiszter tartalmának az alapján meghatározza az éppen végrehajtandó utasítást, és ennek megfelelően működteti a Turing-gép író-olvasó fejét.

---

a Turing-gép alapprogramja és utasításciklusa

A Turing-gép alapprogramja (az ún. átmenetfüggvény) legegyszerűbben egy táblázattal adható meg, amelynek oszlopai a Turing-gép ábécéjének, sorai pedig a Turing-gép lehetséges állapotainak felelnek meg. A táblázat cellái azokat az utasításokat tartalmazzák, amelyek a Turing-gép egyes állapotainak és a Turing-gép ábécéjében levő karaktereknek felelnek meg.

Például egy bináris Turing-gép esetén, amely a szalagon levő bináris karaktersorozat komplementálását végzi el (0 helyett 1, 1 helyett 0 beírását a szalagra)

• legyenek a Turing-gép lehetséges állapotai {s,p,h} ahol
• s az ún. kezdőállapot (start állapot)
• p a "működési" állapot (ebben az egyszerű példában több működési állapotra nincs szükség)
• h az ún. megállási állapot (halt vagy stop állapot)
• legyen a Turing-gép ábécéje {>,0,1,_} ahol
• > a start szimbólum
• _ az üres karakter
• 0 és 1 pedig bináris számjegyek

Ekkor az alapprogramot tartalmazó táblázat a következő lehet:

	>	0	1	_
s	(p,>,jobbra)
p		(p,1,jobbra)	(p,0,jobbra)	(h,_,marad)

(Megjegyzés: a nem kitöltött cellákba bármilyen utasítás írható, mivel ilyen állapotba a Turing-gép nem kerülhet.)

A Turing-gép utasításai három részből állnak, amelyek az utasítás végrehajtása után meghatározzák

1. a Turing-gép új állapotát; ez lehet
• a "működési" állapotok közül valamelyik (esetünkben p)
• a h megállási állapot, amely a Turing-gép leállását eredményezi
2. a szalag aktuális cellájába beírándó új karaktert
3. az író-olvasó fej mozgatását; ez lehet
• léptetés egy cellával balra
• léptetés egy cellával jobbra
• helyben maradás; ilyenkor a gép nem lépteti a fejet

A Turing-gép utasításciklusa

1. egy karakter beolvasása a szalag aktuális cellájából (ez megfelel egy utasítás beolvasásának)
2. a Turing-gép aktuális állapotának beolvasása az állapotregiszterből
3. a Turing-gép aktuális állapotának és a beolvasott karakternek megfelelő utasítás megkeresése a Turing-gép alapprogramjában
4. az utasítás értelmezése, azaz részeire bontása (három részre, ld. fent)
5. az értelmezett utasítás végrehajtása
• az állapotregiszter tartalmának beállítása
• egy karakter kiírása a szalag aktuális cellájába
• az író-olvasó fej léptetése
6. az állapotregiszter tartalmától függően a Turing-gép működésének leállítása (ez megfelel a megszakításkérések vizsgálatának)
7. az utasításciklus újrakezdése

Egy bonyolultabb példa: 1 hozzáadása egy bináris számhoz
 

	>	0	1	_
s	(q0,>,jobbra)
q0		(q0,0,jobbra)	(q0,1,jobbra)	(q1,_,balra)
q1	(h,>,jobbra)	(h,1,marad)	(q2,0,balra)
q2	(q3,>,jobbra)	(h,1,marad)	(q2,0,balra)
q3		(q4,1,jobbra)	(q5,1,jobbra)
q4		(q4,0,jobbra)	(q5,0,jobbra)	(h,0,marad)
q5		(q4,1,jobbra)	(q5,1,jobbra)	(h,1,marad)

A fenti alapprogramhoz tartozó Turing-gép esetén

• a Turing-gép lehetséges állapotai {s,p,h} ahol
• s a kezdőállapot
• q0, q1, ..., q5 a gép működési állapotai
  • q0: a gép megkeresi a bináris szám végét
  • q1: hozzáad 1-et a legkisebb helyiértékű bithez
  • q2: hozzáad 1-et a következő bitekhez
  • q3: beszúr 1-et a legmagasabb helyiértékű bit elé
  • q4: eltolja jobbra a 0 értékű biteket
  • q5: eltolja jobbra az 1 értékű biteket
• h a megállási állapot
• a Turing-gép ábécéje {>,0,1,_} ahol
• > a start szimbólum
• _ az üres karakter
• 0 és 1 pedig bináris számjegyek

A fenti Turing-gép kezeli azt a "kivételt", amikor nincs megadva a szalagon egy bit sem a q1 állapotban, a (h,>,jobbra) leállító utasítással.

további információk:
Turing-gép (2016-11-08)