Chapter 6. Nemdeterminisztikus Turing-gépek

Az eddigiek során megismerkedtünk a Turing-gép alapvető modelljeivel. Ebben a fejezetben a modellek egy általánosításával a nemdeterminisztikus üzemelés bevezetésével foglalkozunk.

6.1. Nemdeterminisztikus Turing-gépek definíciója

Az egyszerűség kedvéért csak az szalagos nemdetreminisztikus Turing-gép definícióját adjuk meg, de természetesen a determinisztikus Turing-gépekhez hasonló módon a többszalagos modell is precízen leírható. A későbbiekben látni fogjuk, hogy nem feltétlenül szükséges, de amennyiben egyértelműen nemdeterminisztikus Turing-géppel dolgozunk, a jobb megkülönböztethetőség érdekében helyett jelölést fogunk használni.

6.1. Definíció

A  ötöst 
               
nemdeterminisztikus 
               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
         

Az előbbi definícióban használt jelölés a az halmaz hatványhalmazát jelöli. A hatványhalmaz az adott halmaz részhalmazaiból álló halmaz:

. A definíció értelmében a függvény az argumentumaihoz nem egy konkrét értéket, hanem értékek egy halmazát rendeli.

Az eddigi Turing-gépeket, megkülönböztetésül az új nemdeterminisztikus modelltől, determinisztikus Turing-gépeknek fogjuk nevezni.

Ahhoz, hogy értelmezni tudjuk az új modellt, hasonló fogalmakat kell bevezetnünk, mint a determinisztikus Turing-gépek esetén.

A determinisztikus modellhez teljesen hasonló módon definiálhatjuk a nemdeterminisztikus Turing-gépek konfigurációját.

6.2. Definíció

A  nemdeterminisztikus Turing-gép egy konfigurációja
 
            .

6.3. Megjegyzés

Itt is igaz a determinisztikus Turing-gépeknél megfigyelt szabály, 
miszerint egy  nemdeterminisztikus Turing-gépnek csak akkor 
létezik  alakú konfigurációja, ha  vagy .
Észrevehetjük még, hogy a nemdeterminisztikus Turing-gépek 
konfigurációit semmi sem különbözteti meg a determinisztikus 
Turing-gépekétől. 

Az igazán fontos és érdekes különbség a determinisztikus és nemdeterminisztikus Turing-gépek között a működésükben található.

6.4. Definíció

Azt mondjuk, hogy a  nemdeterminisztikus Turing-gép egy lépésben 
(vagy közvetlenül) átmehet 
            -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

A definíció alapján azt mondhatjuk tehát, hogy a nemdeterminisztikus Turing-gépek nem átmennek egy konkrét, hanem átmehetnek egy lehetséges konfigurációba. Hogy még pontosabban megértsük a definíciók közötti eltérést nézzük meg hogyan változik a számítás fogalma.

6.5. Definíció

A  nemdeterminisztikus Turing-gép egy lehetséges 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ó
3. , ha nem létezik -ből közvetlenül elérhető konfiguráció. 

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

A  konfigurációról azt mondjuk, hogy elérhető a  konfigurációból, 
   ha a Turing-gépnek van  számítása. 

Ha  elérhető -ból, és , 
akkor azt mondjuk, hogy a számítás -hez tartozó ága véges, a 
Turing-gép ezen az ágon a  végállapotban megáll. 
Ekkor a  szót  
               egy kimenetének nevezzük.

A nemdeterminisztikus Turing-gépek kimenete a következőképpen 
megadott halmaz:
.

A helyes értelmezéshez hozzá tartozik, hogy a lehetséges konfigurációváltások között nincs kiemelt, nincs valószínűsége az egyes lépéseknek (mint sztochasztikus automaták esetén), hanem úgy tekintendő, mintha a lehetséges irányok mindegyikében folytatódna a számítás. (A Turing-gép az egyes konfigurációk után továbblépésnél "osztódik".)

Példák

1. Legyen , ahol , , és

:

.

A Turing-gép kimenete az üres szón: .

A Turing-gép lehetséges számításai egy végtelen fastruktúrával írhatók le:

Az ábrán zöld színnel a kezdőkonfigurációt, pirossal a megálló konfigurációkat jelöltük.

2. Legyen , ahol , , és

:

.

A Turing-gép kimenete az üres szón: .

3. Legyen , ahol , , és

:

.

A Turing-gép kimenete az üres szón: .

Hasonlóan a determinisztikus Turing-gépekhez, itt is definiálhatjuk a felismerő Turing-gép fogalmát. A nemdeterminisztikus Turing-gépek működéséből adódóan azonban ez kicsit másképp értelmezhető mint a determinisztikus esetben.

6.6. Definíció

Legyen  egy nemdeterminisztikus Turing-gép, 
 és . 
Ekkor  nemdeterminisztikus elfogadó Turing-gépnek nevezzük, 
a -beli állapotokat pedig elfogadó állapotoknak. 

6.7. Definíció

Legyen  egy nemdeterminisztikus elfogadó Turing-gép, 
 a  elfogadó állapotainak halmaza. 
Azt mondjuk, hogy  elfogadja a  szót, hogy ha van -nek 
olyan véges számítása a  bemeneten, amelyik végén megálláskor 
-beli állapotban van.

6.8. Definíció

Legyen  egy nemdeterminisztikus elfogadó Turing-gép.
Az  nyelvet a  által felismert 
nyelvnek nevezzük.

Azt mondhatjuk tehát, hogy egy nemdeterminisztikus Turing-gép elfogad egy szót, ha van olyan számítása, amely elfogadja. Mindeközben azonban lehet olyan számítása is, amely elutasítja, ez nem befolyásolja azt, hogy elfogadja-e a Turing-gép. Egy szót akkor nem fogad el egy Turing-gép, ha nincs olyan számítása amelyik elfogadja. Látható, hogy ez általános esetben lényegesen bonyolultabb kérdés, mint determinisztikus esetben, hiszen itt akár végtelen sok számítás is indulhat egy kezdőkonfigurációból.

A determinisztikus Turing-gépek összefűzéséhez hasonlóan nemdeterminisztikus Turing-gépek esetén is lehetőségünk van egyszerűbb gépekből bonyolultabbak felépítésére.

6.9. Definíció (nemdeterminisztikus Turing-gépek összefűzése)

Legyen  és  
két nemdeterminisztikus Turing-gép. 
Tegyük fel, hogy . 
A  (vagy  Turing-gépet a következőképpen 
definiáljuk:
, ahol 
  , , , 
   és . 
Itt
 
ahol 
, minden  esetén, valamint 
 esetén és .

Észrevehetjük, hogy a definícióban az egyik Turing-gépről a másikra való átugrás ugyanúgy egyértelmű mint a determinisztikus Turing-gépeknél, hiszen az ugrást megvalósító állapotokon az átmenetfüggvény értéke egyelemű halmaz.