6.2. Nemdeterminisztikus Turing-gépek szimulációja

Természetes kérdésként merül fel az emberben, hogy milyen kapcsolat van a determinisztikus és nemdeterminisztikus Turing-gépek között. Mennyivel másabb az új definíció és mit jelent ez algoritmikus hatékonyság szempontjából.

Hasonlóan a determinisztikus Turing-gépeknél leírtakhoz, nemdeterminisztikus Turing-gépekre is definiálhatjuk a szimuláció fogalmát.

6.10. Definíció

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

A szimuláció ilyen megfogalmazása azonban csak a nemdeterminisztikus Turing-gépek közötti összefüggések leírására alkalmas. Egy kis módosítással kiterjeszthetjük determinisztikus Turing-gépekre is.

6.11. Definíció

Legyen  egy determinisztikus és  egy nemdeterminisztikus 
Turing-gép. 
Azt mondjuk, hogy  szimulálja -et, 
ha  
és  esetén . 

Első megfigyelésként kimondhatjuk a következő tételt.

6.12. Tétel

Minden  determinisztikus Turing-géphez létezik  
nemdeterminisztikus Turing-gép, amelyik szimulálja -t.

Bizonyítás

Tegyük fel, hogy a szimulálandó Turing-gép . Ez alapján legyen , ahol

és az átmenetfüggvény olyan, amire minden és esetén teljesül az

egyenlőség.

A definíciója következtében minden konfigurációjából legfeljebb egy másik konfigurációba léphet tovább.

Világos, hogy szimulálja -et, mivel -nek tetszőleges bemeneten legfeljebb egy lehetséges számítása van és az pontosan megegyezik számításával, így a kimenetük is megfelel egymásnak. (Ha -nek van kimenete, az mindenképpen egy elemű.) ✓

6.13. Megjegyzés

Az előző tétel bizonyítása szerint minden determinisztikus 
Turing-gépnek egyértelműen megfeleltethetünk egy vele 
lényegében teljesen megegyező nemdeterminisztikus Turing-gépet. 
Ezen megfeleltetés alapján a determinisztikus Turing-gépeket 
beágyazhatjuk a nemdeterminisztikus Turing-gépek halmazába. 
A beágyazás lehetősége miatt így egy determinisztikus 
Turing-gépet tekinthetünk nemdeterminisztikusnak is. 

A tétel alapján kimondhatjuk, hogy minden feladat, ami megoldható determinisztikus Turing-géppel, megoldható nemdeterminisztikus Turing-géppel is. Ez azt jelenti, hogy a nemdeterminisztikus Turing-gép mint számítási modell legalább olyan erős, mint a determinisztikus. Kérdés, hogy ténylegesen erősebb-e, azaz van-e olyan feladat, ami megoldható nemdeterminisztikus Turing-géppel, de nem oldható meg determinisztikussal. Az állítás pontos megfogalmazásához szükségünk van a szimuláció fogalmának megfelelő kiterjesztésére. A nemdeterminisztikus Turing-gépek kimenete nem egyetlen szó, hanem szavak halmaza, így kicsit nehézkesebb lenne megfogalmazni a szimuláció definícióját teljesen általános esetre. Mivel nincs is igazán nagy szükség a későbbiek megértéséhez, ezzel nem is foglalkozunk a jegyzet keretein belül. Felismerő Turing-gépek esetében azonban a fogalom minden különösebb gond nélkül leírható.

6.14. Definíció

Legyen  egy nemdeterminisztikus és  egy determinisztikus 
felismerő Turing-gép. Azt mondjuk, hogy  szimulálja -et, 
ha .

A nemdeterminisztikus Turing-gép modell Turing-ekvivalenciája a következőképpen fogalmazható meg.

6. 15. Tétel

Minden  nemdeterminisztikus felismerő Turing-géphez létezik  
determinisztikus Turing-gép, amelyik szimulálja -t.

Bizonyítás

A tétel igazolását konstruktív módon végezzük. Mivel azonban a pontos bizonyítás sok apró technikai részlet leírásával járna, csak a vázlatát adjuk meg.

Legyen

a szimulálandó nemdeterminisztikus Turing-gép.

A szimuláció alapötlete az, hogy a szimuláló Turing-gép szélességi kereséssel bejárja teljes számításfáját. Egészen pontosan, addig keres a számításfában, amíg

a.) vagy meg nem talál egy elfogadó állapotú konfigurációt,

b.) vagy el nem fogynak a folytatható konfigurációk.

-nek két szalagja lesz. Az elsőn fogja tárolni azt a konfigurációt, amelyikből a továbblépési lehetőségeket számolja, míg a második egy FIFO szerkezetű tárolóként szolgál, amin a megvizsgálandó konfigurációkat tárolja.

A működés pontosabb leírása a következő:

1. Az . szalagon levő bemenő szó alapján a. szalagra előállítja a szimulálandó kezdőkonfigurációját, majd mögé ír egy megfelelő elválasztójelet pl.).

2. Megvizsgálja, hogy üres-e a . szalag. Ha üres, megáll nem elfogadó állapotban, egyébként folytatja a 3. lépésnél.

3. A . szalagról az -re másolja az első ott található konfigurációt, miközben le is törli onnan.

4. Megvizsgálja, hogy az . szalagon levő konfiguráció elfogadó végállapotban van-e. Ha igen, megáll elfogadó állapotban, egyébként folytatja az 5. lépéssel.

5. Megvizsgálja, hogy az . szalagon levő konfiguráció nemelfogadó végállapotban van-e. Ha igen, letörli az . szalagot, és folytatja az 2. lépéssel, egyébként továbblép a 6. lépésre.

6. Egy előre rögzített sorrendben végigmegy a átmenetfüggvénye által meghatározott konfigurációátmeneteken, de nem végrehajtja őket, hanem egymás után elválasztó jelekkel elkülönítve a . szalag végére írja őket. Ha mindet kiírta, folytatja a 2. lépéssel.

Az így megadott determinisztikus Turing-gép megfelelő sorrendben szélességi bejárással végiglépked a összes lehetséges számításának összes konfigurációján mindaddig, míg elfogadó állapotot tartalmazó konfigurációhoz nem ér. Ha ilyet talál, elfogadja a bemenetet és megáll. Ha elfogynak a bejárható konfigurációk (azaz a számításfa véges) nemelfogadó állapotban megáll. Ha a számításfa nem véges, de nincs benne elfogadó állapotú konfiguráció, végtelen ciklusba kerül.

A leírás alapján világos, hogy pontosan azokat a szavakat fogja elfogadni, amelyeket , azaz .✓

6.16. Megjegyzés

1. A tétel alapján tehát azt mondhatjuk, hogy a nemdeterminisztikus 
Turing-gép modell sem erősebb, mint a determinisztikus, azaz ha egy 
probléma megoldható nemdeterminisztikus Turing-géppel, akkor 
megoldható determinisztikussal is.
2. Ha  egy nyelv, és létezik  nemdeterminisztikus Turing-gép, 
amelyikre  akkor .