Savitch tétele (1970):
NSZÉR (f(n)) ⊆ DSPACE (f²(n)).Vagyis ha egy nem determinisztikus Turing-gép meg tud oldani egy feladatot f ( n ) memória használatával, akkor egy determinisztikus Turing -gép meg tudja oldani a memória négyzetére.
| Bizonyíték: |
| Vegyünk egy Turing-gépet bemenettel és munkaszalaggal. Konfigurációja a következőképpen kódolható: kódolja a munkaszalag helyzetét és tartalmát (memóriát foglal), a bemeneti szalag helyzetét (memóriát foglal). Azóta a konfiguráció mérete a következő lesz.
Hadd . Aztán van egy nem determinisztikus Turing-gép, amely felismeri ezt a nyelvet. Vegyünk egy olyan segédfunkciót, amely legfeljebb átmenetekben számítja ki a konfigurációból a konfigurációba való átmenet lehetőségét: Elérés (I, J, k): ha (k = 0) visszatérés (IJ) vagy (I = J) // rekord (IJ) azt jelenti, hogy az MT egy lépésben áthelyezhető az I konfigurációból a J konfigurációba else for (Y) // köztes konfigurációk felsorolása , ha Reach(I, Y, k-1) és Reach(Y, J, k-1 ) true return hamisEz a funkció rekurziós mélységgel rendelkezik, a rekurzió minden szintjén a memóriát használja az aktuális konfigurációk tárolására. Tekintsünk egy nyelvet felismerő Turing-gépet. Ennek a gépnek lehetnek konfigurációi. Ennek magyarázata a következő. Legyen rajta a szalag ábécé állapotai és szimbólumai. A munkaszalagon megjelenő különböző sorok száma. A bemeneti szalag feje lehet az egyik pozícióban és az egyik munkaszalagban. Így az összes lehetséges konfiguráció száma nem haladja meg a -t. Tekintsünk egy függvényt, amely adott szó esetén ellenőrzi, hogy az a nyelvhez tartozik-e: Ellenőrizze (x, L): ( T) esetén // ismételje meg azokat a konfigurációkat, amelyek elfogadó állapotokat tartalmaznak, ha a Reach(S, T, ) true return falseHa a szó a nyelvhez tartozik, akkor be lesz fogadva, mivel minden lehetséges bekerülési utat mérlegelnek. Ezt a függvényhez számunkra megadott rekurziós mélység biztosítja. És ha egy szó nem engedélyezett lépésenként (az összes lehetséges konfiguráció száma), akkor garantáltan nem engedélyezett. Ennek eredményeként a függvény rekurziós mélységgel rendelkezik, a rekurziós memória minden szintjén használatos. Ekkor az összes funkció memóriát használ. |