4.6. Többszalagos Turing-gépek, szimuláció

Az eddig megismert Turing-gép modell általánosításaként bevezetjük a többszalagos Turing-gépek fogalmát. Itt a Turing-gép állapotregisztere egynél több szalaggal is kapcsolatban állhat, azokhoz külön író-olvasó fejjel rendelkezik, melyeket egymástól függetlenül mozgathat.

Figure 4.39. Többszalagos Turing-gép

Többszalagos Turing-gép

4.27. Definíció (többszalagos Turing-gép)

Legyen , egész szám. A  
               -ost -szalagos Turing-gépnek 
nevezzük, ha
    véges, nem üres halmaz; állapotok halmaza
     véges, nem üres halmaz, ; szalag ábécé
   ; kezdő állapot
   , nem üres; végállapotok halmaza
   ; átmenetfüggvény

Hasonlóan az egyszerű (egy szalagos) Turing-géphez, definiálhatjuk a konfiguráció, konfigurációátmenet és számítás fogalmát.

4.28. Definíció

Legyen  egy -szalagos Turing-gép és
.
-t a  
            lehetséges konfigurációi halmazának, elemeit  lehetséges
konfigurációknak nevezzük.
Ekkor  a  
            egy szalagjának lehetséges leírásait tartalmazó halmaz.

4.29. Definíció

Legyen  egy -szalagos Turing-gép és  két 
konfigurációja. Tegyük fel, hogy


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

4.30. Megjegyzés

Többszalagos Turing-gép esetén egy lépés során szalagonként 
függetlenül - bár az átmenet függvény által közösen meghatározott 
módon - végzünk műveleteket.

4.31. Definíció

Legyen egy -szalagos Turing-gép.
 egy számítása az  hosszúságú  bemeneten konfigurációk egy
 sorozata amelyekre
1. , ahol  és
    , ha ;
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ó.

Ha  olyan, hogy , akkor azt mondjuk, hogy a számítás 
véges, a Turing-gép a  végállapotban megáll. Ha ekkor , 
akkor 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.32. Megjegyzés

A többszalagos Turing-gép definíciójában feltételeztük, hogy a 
bemenetet az első szalagon adjuk meg és a kimenetet ugyanoda írjuk 
vissza. Ez pusztán megállapodás kérdése. Természetesen egyedi 
esetekben más - esetleg több - szalag is tartalmazhatja a bemenetet 
vagy a kimenetet.

Világos, hogy a frissen definiált többszalagos Turing-gép modell legalább olyan erős, mint az eredeti, egyszerű egyszalagos, hiszen minden egyszalagos Turing-gép kiegészíthető tetszőleges számú szalaggal, amelyeket menet közben nem használunk. Működés szempontjából teljesen azonosnak tekinthetők az egy- és belőle készített többszalagos Turing-gépek.

Ahhoz, hogy az egyes modellek erősségét megvizsgáljuk, először is szükségünk lesz egy pontos definícióra, ami elég kifejezően leírja a modellek viszonyát. Ennek segítségével az új és régi modellt össze tudjuk hasonlítani.

4.33. Definíció

Legyen ,  két Turing-gép. Azt mondjuk, hogy  szimulálja -et, 
ha  és  esetén . 

4.34. Megjegyzés

Az előző definíció alapján  tetszőleges bemenete lehetséges bemenete
 -nek is. 
Továbbá,  azt jelenti, hogy ha  megáll a  bemeneten és 
kimenetként egy  szót ad, akkor  is megáll és szintén -t ad 
válaszul. Ha  nem áll meg a  bemeneten, akkor  sem.
Elképzelhető, hogy  sokkal több mindent ki tud számolni, mint , más 
bemeneteket is kaphat, de azt mindenképpen meg tudja csinálni, amit .

4.35. Tétel

Legyen ,  egy -szalagos Turing-gép. Ekkor létezik -t 
szimuláló -szalagos  Turing-gép.

Bizonyítás

A precíz bizonyítás meglehetősen sok technikai részlet kidolgozását igényelné, ezért csak a vázlatát ismertetjük.

Konstruktív módon látjuk be az állítás igazságát, ami azt jelenti, hogy nem egy általánosan létező Turing-gépről fogunk igazolni valamit, hanem megadjuk a konkrét felépítését is.

A szimuláció alapötlete az, hogy lépésről-lépésre végrehajtjuk az eredeti Turing-gép adott inputon elvégzett számítását. Ehhez a szimuláló Turing-gép folyamatosan tárolja a szimulált Turing-gép aktuális konfigurációit. Általánosan megfogalmazható, hogy adattárolásra kétféle lehetőség adódik: az állapoton keresztül vagy a szalagon. Mivel az állapotok segítségével csak véges mennyiségű adat tárolható, a konfigurációk száma pedig végtelen, természetes módon adódik, hogy a szalagon tároljuk a szükséges információt. Mivel a szimuláló Turing-gépnek csak egyetlen szalagja van, így azon az egyetlen szalagon kénytelen tárolni a szimulált Turing-gép teljes szalagtartalmát. Ennek megoldására több lehetőség is adódik. Az egyik az lehet, hogy a szimulált Turing-gép szalagjain levő szavakat a szimuláló Turing-gép szalagján egymás után, valamilyen határolójelekkel elválasztva tároljuk. Ekkor az jelent külön problémát, hogy a szavakhoz való hozzáírás vagy azokból való törlés esetén a többi szót folyamatosan mozgatni kell, hogy ne veszítsünk el egyetlen értékes jelet sem, illetve, hogy az ábrázolt szavak ne távolodjanak el egymástól. Egy másik megközelítés - amit végül is követni fogunk a bizonyítás során -, hogy az egyetlen szalagot "sávokra" bontjuk úgy, mintha továbbra is meglennének a korábbi szalagok, csak az író-olvasó fejeik mozgása egymáshoz rögzített lenne. Ekkor (akárcsak az előbbi modellnél) szükséges az eredeti Turing-gép író-olvasó fejeinek pozícióját tárolni. Ez utóbbi megoldást követve a szalag-abc jelei az eredeti szalag-abc jeleiből képzett komponensű vektorokként képzelhetők el, kiegészítve az író-olvasó fejek helyének jelölésére szolgáló komponensű vektorral.

Lássuk az előbb leírtaknak megfelelő definícióját.

Legyen a -t szimuláló Turing-gép, ahol

és

az átmenet függvény, amit az alábbiakban írunk le.

A bizonyítás elején leírtaknak megfelelően szalagján fogjuk tárolni az eredeti Turing-gép szalagjairól származó összes információt. Eközben állapota tárolja többek között aktuális állapotát.

A egy konfigurációjának kiindulásképpen a következő konfigurációját fogjuk megfeleltetni: .

egyes összetevőit a következőképpen adhatjuk meg:

,

, ahol ha és , illetve egyébként,

valamint

, ahol (azaz hossza eggyel hosszabb, mint a szalagjain levő szavak leghosszabbikának hosszával),

minden esetén, ahol (ha akkor legyen ) és

, ha illetve egyébként (azaz az író-olvasó fej az . szalagon levő szó . betűjén áll), minden és esetén.

Egy konkrét -szalagos Turing-gép esetén ez a következőképpen néz ki:

Figure 4.40. Egy kétszalagos Turing-gép szimulációja

Egy kétszalagos Turing-gép szimulációja

A Turing-gép egy ilyen kiindulási konfigurációból a következő számítási fázisokat hajtja végre:

1. fázis: Beolvasás.

Végig lépked a szalag értékes celláin, és ahol az író-olvasó fej pozíciójában -t talál, a megfelelő szimbólumot beírja az állapotának megfelelő pozíciójába.

Az előbbi példában a negyedik lépésig változatlan, utána viszont értéket vesz fel. Az ötödik lépés után pedig megint változik, a értékre.

Ha a szalag utolsó értékes celláját is megvizsgálta átlép a következő fázisba.

Tovább vizsgálva a példát, állapota már nem változik ebben a fázisban, mivel nincs több író-olvasó fej a szalagon.

2. fázis: $T'$ lépésének végrehajtása.

Ebben a fázisban összesen egy dolgot csinál: ha , akkor átmegy a állapotba, ahol

Itt lényegében kiszámolja és eltárolja az állapotában, hogy a szimulált Turing-gép milyen állapotváltozáson megy keresztül és milyen módon változtatja meg a szalagtartalmakat, vagy az író-olvasó fejek helyét.

Ezután átlép a harmadik fázisba.

3. fázis: Visszaírás.

A megváltozott állapot tartalma alapján átállítja a szalagtartalmat. Visszafelé lépkedve megkeresi az író-olvasó fejek helyét jelölő -eket, és ha talál egyet, megnézi, hogy milyen műveletet kell végrehajtania. Ha cserélni kell az eredeti Turing-gép szalagján levő szimbólumot, akkor a megfelelő -t kicseréli -re, ha mozgatni kell az író-olvasó fejet, akkor törli az értéket a cella megfelelő komponenséből és a szomszédos cella megfelelő komponensébe írja át (jobb- vagy baloldali szomszéd, a értékének megfelelően).

Ezek a lépések az összetettségük miatt nem hajthatók végre egyetlen állapot segítségével, ezért menet közben utolsó komponensét értelemszerűen változtatni kell. (-mel jelölhetjük a fázison belüli különböző műveleteket),

Ha elérte a szalag elejét, átlép a negyedik fázisba, amit $ komponenssel jelölhetünk.

4. fázis: Kiigazítás.

Ez a fázis a legkomplikáltabb. Amennyiben valamelyik szalagjának elején hozzáír vagy töröl egy szimbólumot, akkor a szalagján elcsúsznak egymáshoz képest a szalagkezdetek. Ezt normalizálni kell, hogy ugyanolyan típusú konfigurációból indulhasson a következő lépés szimulálása, mint az előzőben.

Amennyiben a kiigazítással végzett, kétféleképpen folytathatja a számítást.

Ha a állapot $q''$ komponense végállapot, akkor átmegy a állapotba, ha nem végállapot, akkor pedig a állapotba. Ez utóbbi esetben a Turing-gép az 1. fázisnak megfelelő kiindulási konfigurációba kerül, és folytatja a számítást (az 1. fázis lépéseivel).

Amennyiben a Turing-gépet a kezdőkonfigurációjának megfelelő kiindulási konfigurációból indítjuk látható, hogy a 4.-1. fázisátmenet során pontosan a számításának megfelelő konfigurációkon halad végig. Megállni pontosan akkor fog, ha az eredeti Turing-gép is megállt volna, a szalagtartalma pedig (megfelelő értelmezés mellett) pontosan a szalagtartalmának felel meg. Azaz valóban szimulálja -t. ✓

Feladat:

1. Írjunk Turing-gépet az Ackermann-függvény kiszámítására!